Sample Complexity of Interventional Causal Representation Learning
Authors: Emre Acartürk
Burak Varıcı
Karthikeyan Shanmugam
Ali Tajer
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal representation learning
sample complexity
interventions
score-based methods
identifiability
Primary area: causal_inference
TL;DR: First sample complexity analysis for interventional causal representation learning.

Abstract: Consider a data-generation process that transforms low-dimensional _latent_ causally-related variables to high-dimensional _observed_ variables. Causal representation learning (CRL) is the process of using the observed data to recover the latent causal variables and the causal structure among them. Despite the multitude of identifiability results under various interventional CRL settings, the existing guarantees apply exclusively to the _infinite-sample_ regime (i.e., infinite observed samples). This paper establishes the first sample-complexity analysis for the finite-sample regime, in which the interactions between the number of observed samples and probabilistic guarantees on recovering the latent variables and structure are established. This paper focuses on _general_ latent causal models, stochastic _soft_ interventions, and a linear transformation from the latent to the observation space. The identifiability results ensure graph recovery up to ancestors and latent variables recovery up to mixing with parent variables. Specifically, ${\cal O}((\log \frac{1}{\delta})^{4})$ samples suffice for latent graph recovery up to ancestors with probability $1 - \delta$, and ${\cal O}((\frac{1}{\epsilon}\log \frac{1}{\delta})^{4})$ samples suffice for latent causal variables recovery that is $\epsilon$ close to the identifiability class with probability $1 - \delta$.

Sample Complexity of Interventional Causal Representation Learning
Emre Acartürk Rensselaer Polytechnic Institute
Burak Variet Carnegie Mellon University
Karthikeyan Shanmugam Google DeepMind
Ali Tajer Rensselaer Polytechnic Institute
Abstract
Consider a data-generation process that transforms low-dimensional latent causally- related variables to high-dimensional observed variables. Causal representation learning (CRL) is the process using the observed data to recover the latent causal variables and the causal structure among them. Despite the multitude identifiability results under various interventional CRL settings, the existing guarantees apply exclusively the infinite-samplle regime (i.e., infinite observed samples). This paper establishes the first sample-complexity analysis for the finite-sample regime, in which the interactions between the number of observed samples and probabilistic guarantees on recovering the latent variables and structure are established. This paper focuses general latent causal models, stochastic soft interventions, and a linear transformation from the latent to the observation space. The identifiability results ensure graph recovery up ancestors and latent variables recovery to mixing with parent variables. Specifically, O(log } samples suffice for latent graph recovery up to ancestors with probability 1 8, and O({2 log })*) samples suffice for latent causal variables recovery that is close to the identifiability class with probability 1-6.
Introduction
The observed data generated in a wide range technological, social, and biological domains has high-dimensional, complex, and often unexplainable structures. Nevertheless, sometimes, such complex structures can be explained by latent generating factors that often form lower-dimensional structures. The field of causal representation learning (CRL) motivated by this premise and focuses on disentangling the cansally-related latent generating factors that underlie a given high-dimennional observable dataset. In particular, given a high-dimensional dataset, the objective of CRL is to learn (i) the underlying latent causal variables and (ii) the causal relationships among the latent variables. The learned representations then provide an explainable structure for the observed data and facilitate informed reasoning for the downstream tasks [1].
Formally, CRL consists of data generation and data transformation pipeline follows. There exists set of high-level latent variables Z E R that are causally related. The causal interactions captured by directed acyelic graph (DAG) G. The latent variables Z go through unknown transformation and generate the observed variables X E Rd, i.e., X = g (Z). The objective of CRL is use the observed variables X and learn the latent graph G and latent variables Z. The primary question facing CRL identifiabilit, which refers to establishing the conditions under which recovering Z and are possible.
WWok was done while BV Ph.D. student at Rensselaer Polytechnic Institute.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Identifiability is known to be impossible without proper inductive biases or additional supervision [2. 3.. One approach address this issue is performing interventions leading to interventional CRL which has gained significant recent attention [4, 5, 6, 7, 8, 9, 10j. Specifically, interventions on latent causal variables create additional statistical diversity in the observed data. Accessing to enough interventional environments enables identifiability [1]. Despite the recent advances in establishing identifiability guarantees for interventional CRL, all the existing guarantees focus on the asymptotic infinite-sample regime, where one assumes access to an infinite number of observable samples X.
In this paper, we establish conditions for finite-sample non-asymptotic identifiability and perfor- mance guarantees for interventional CRL. We focus on CRL under the general (non-pat noon-arammttrc) latent causal models, soft interventions, and linear transformations from the latent to the observation space. This setting is well-studied in the infinite-sample regime [4, 5, 7, 11], where the existing identifiability results show that the causal graph can be recovered up to ancestral nodes, and latent variables can be learned up to mixing with their ancestors. In this paper, we provide the probabilistic inite-sample counterparts of these identifiability guarantees and establish the first sample complexity analysis for interventional CRL in the finite-sample regime.
Our CRL approach falls in the category of score-based CRL [5], based on which our sample complexity analysis consists of two steps. In the first step, we delineate a general sample complexity for any desired consistent score estimator. Subsequently, we specialize these general results by adopting the reproducing kernel Hilbert space (RKHS)-baaa -based score estimator [12]. We establish the following identifiability guarantees for any desired pair of constants c, 6 E I...
Latent graph recovery: Using RHKS-based score estimator, O(log }) samples suffice to recover the transitive closure of the latent graph with probability at least 1 - 5.
Latent variables recovery: Using the same score estimator, (((2 log })²) samples suffice to ensure that the mean squared error in the estimated latent causal variables is at most e² with probability at least 5.
Dependence on model dimension: We further establish the explicit and implicit dependence of sample complexity on the dimensions of the latent and observable spaces, и and d, respectively. The precise characterizations of these expressions involve additional model-dependent constants specified in Section 5.
Finally, note that latent variables recovery result, where we show recovery up to mixing with parents, which improves upon the results in existing literature that guarantee recovering up to mixing with ancestors.
Improved guarantees:
Methodology. We offer novel finite-sample CRL algorithms and characterize the sample complexity guarantees achievable by these algorithms. We design our algorithms using the properties of score functions (i.e., the gradient of the log density). This approach is inspired by the score-based CRL framework [5, 8]. However, the algorithms are significantly different, led by the need to integrate finite-sample score estimation routines and their imperfections. In our analysis, first, provide sample complexity upper bounds for a score- score-based framework that uses any desired consistent score difference estimator. Then, adopt specific score estimator [1 [12] and provide explicit sample complexity guarantees.
Related work. All the existing studies interventional CRL focus the infinite- sample regime. We briefly review the studies that adopt a similar CRL model, i.e., linear transformations and single- node soft interventions. In this setting, complete identifiability results for linear latent models are established in [7]. Similar results are shown for nonlinear latent causal models in [4, 11] and for linear non- Gaussaan models in [13]. In the most closely related setting to ours, identifiability up to ancestors is shown to be possible using soft interventions on general latent causal models [8]. Other studies on interventional CRL include using do interventions for polynomial transformations [6. 14] and hard interventions for general transformations [10, 8). On a partially related problem, error rates for using score functions on observed causal discovery are provided in [15].
Vectors are represented by lower case bold letters, and element of vector is denoted by v,. Matrices are represented by upper case bold letters, and we denote row i and column j of matrix A by A;, and A.,, respectively. The row permutation matrix for permutation æ of [n] is denoted by P.. Random variables and their realizations are presented by upper and lower case letters, respectively. We denote the Moore-Penrose pscudoinverse
Notations. For n E N. we define [n]

---

of matrix A by At, Given a symmetric matrix A E Raxd, we denote the vector of eigenvalues of
A ordered in ascending order by X(A) IR' and the matrix of eigenvectors by Q(A) R such that A (() diag A(A)) Q(A) TT For any matrix A, we denote the rank, column, and null spaces of A by rank A), col A), and (A), respectively.
2 Finite-sample data-generation process
The existing studies on analyzing the identifiability guarantees of CRL inevitably necessitate the availability of an infinite number of samples otherwise, perfect identifiability is rendered impossible. In this paper, our objective is identifiability analysis assuming only a finite number of samples are available significant departure from the infinite-sample sample regime. In this section, we specify a general data-generating process consisting of a latent causal space and an unknown linear transformation that maps the latent variables observed variables.
Latent causal model. We have a latent space of n causally related random variables. We denote the latent causal variables by & [Z....., Zn,]² The causal relationships among the variables of are represented by directed acyclic graph G with n nodes where the i-th node represents Z.. We denote the parents, children, and ancestors of a node E [n]] in & by pa(i), ch(i), and an(i), respectively. We denote the probability density function (pdf) of Z by pz. which is assumed to be well-defined without any zeros over lwwer-dimensionll manifolds and to have full support on R". Given the DAG G, pz factorizes according to
(2())=
II pe(2s 2pa(t)) sE(n]
(1)
We assume that the conditional pdfs (p: : E [n]] are continuously differentiable with respect to 2. We call a permutation implies π; < J.. Without loss of generality, we assume that (1...., n) is a valid causal order.
- mn) of [m] valid causal order if for all i, [ni, E pa(j)
Transformation model. The latent variables Z are mapped to the observed variables X - (Xi,... Xa] through an unknown linear transformation G E Rddn,, where d 2 n. Specifically,
X= Z. Z,
where G has full column rank. We denote the pdf of X by px- Note that owing to the generation process of X, the pdf px is supported on an n-dimensional subspace embedded in Rdd We denote the I norm of any function f with finite variance under px by Il & Epx (=)
Intervention model. We consider CRL under interventions, and in particular focus on soft inter- ventions, the most general form of interventions. Hence, in addition to the observational model specified by (2), we consider n single-node interventional environments {E : m E [n]]] We assume that the node intervened the environment m unknown and denote by 1 Leaving one node unintervened renders identifiability impossible [7]. Hence, we inevitably have {1 m E [n]] = [n].
Applying soft intervention node i changes its causal mechanism specified by the observa- tional conditional pdf (2 *pa(i) ) to a distinct interventional conditional pdf q:(2; >pa()))
The conditional pdfs {q: i E [n]] are assumed to be continuously differentiable with respect to z. Subsequently, the pdf of Z in the interventional environment mm denoted by p", factorizes according to
2Z (2) ge(ee (pp(())
IIx(2z 2pa(t)) where t= 1
To distinguish the observational and interventional data, we denote the latent and observed random variables in environment gd by z and X respectively. Interventions do not alter the transforma- tion matrix G. indicating that similarly to (2), we have X G nmm Throughout the paper, we adopt the convention that Eo refers the observational environment.
Score functions. The score function associated with a pdf is defined as the gradient of its logarithm. We denote the score functions associated with the observational distributions of Z and X by sz and sx, respectively, i.e.,
sz(2) (z)) and sx(x) A V logpx(x).
(4)
3

---

Similarly. we denote the score functions associated with the distributions of Z and X in environment 9 for E [n] by am and x respectively, i.e..
82 (=) V log (z) and xx V logg"
(5)
In our algorithm and analysis, we will analyze the score variations across different interventions. For this purpose, we define the score difference functions of Z and X between environments e and g as
(2) - 22 (2) sz(z), and dx(x) x (z)
sx(x), Vm E [n]
(6)
To ensure that interventions affect the target node and its parents distinctly, we adopt the following assumption. This assumption holds for large class of models, e.g., additive noise models under stochastic hard interventions [5, Lemma 2].
[n]] and for all k pa((")), the term Assumption (I5, Assumption 1]). For any (ld2) /// [dz Im) is not a constant function of
Finite sample data. We assume that we have only N data samples under each of the environments. We denote the N samples of z and X by
{=] j [N]} and {xp :j [N]] Vm (0) [m)]
Accordingly, for each sample j. we concatenate all latent and observational samples under different environments to create sample matrices
Z,
21 and
X, -
Vj E [M].
(8)
Finally, we define the set of samples XN
(X, j E [N]] and ZN - z j E [N]]
3 Finite-sample identifiability objectives
The CRL framework specified in Section 2 has objectives: the N observational samples XN {X, : e [N]] to recover the causal graph G and the latent causal variables Z = (Z, j E [A]]. In this section, we formalize the inference rules and their associated fidelity metries for recovering G and Zx.
Latent graph recovery. Define & as the set of all DAGs on n nodes. We define as a generic estimator of the latent graph G, i.e.,
g: (Rdx(+11)) +8.
To quantify the accuracy the estimate (Nv)), we provide the following probably approximately correct (PAC) guarantee, which is the probabilistic counterpart of the standard identifiability up to ancestor definition in the interventional CRL literature [5, 7, 11].
Definition (6-PAC graph recovery). Graph estimate ((Xx) achieves 8-PAC latens graph recovery if. with probability at least 1 - 6, the transitive closures of ((Xx) and G are isomorphic.
Latent variables recovery. We investigate two-step estimator for the latent variables Zn. First, define a generic estimator for the pseudoinverse of as
H: (Rdx(++1)) N na
(10)
Then, given an estimate H(Xx) for G we estimate [Z j E [N]) according to
2, H(Xx) X;,
Vj E [N]
(1))
We provide the following definition to quantify the fidelity of these estimates with respect to the ground truth variables.
Definition 2 ((c,5) 5 variables recovery). The estimate H(Xx) achieves ( latent variables recovery if the estimated causal variables {Z, : [N]] satisfy
2 = Pr (Cpa - C.r) Z; where for all i & pa(j), Cpa satisfies (Cpa)i.j = 0, and, with probability least we have |Cerre <
(12)

---

We note that Definition 2 is the probabilistic counterpart of the standard identifiability up to ancestor definition in interventional CRL literature.
Noisy score model. The score-based CRL framework uses properties of score function differences to build the estimators for the latent graph and variables. Therefore, when we only have access finite data, we need to estimate the score functions, We denote generic score function estimator for environment r by
(x XN): R2 (I))(*+)))) + R
(13)
When the dependence is clear from the context, we will drop the explicit dependence of 8 on XN- Similarly to (6), we define the estimated score difference functions
dx (z; XN) s [z; Xx) 3x (z; AN), Vm E [ni]
(14)
In this paper, we focus consistent score difference estimators (dx m E [m]], i.e., they satisfy convergence probability. Specifically, for any 6, > there exists N(e, N such that
max mE
[xx((;
VA 2 (), px I 2 1
(15)
Notably, we note that many score estimators are known to be consistent [12, 16, 17, 18).
4 Finite-sample CRL algorithms
In this section, we design finite-sane sample interventional CRL algorithms through which we establish finite-sample identifiability guarantees as well as bounds on the associated sample complexities. Our algorithms fall within the score-based category of CRI. algorithms [5]. The main intuition of this framework is that score functions in the observed space contain all the information needed for recovering the latent graph G and the inverse transform Gt, Specifically, two metrics are pivotal for retrieving the latent space:
1. Score differences: As shown in Lemma 1, the nonzero entries of the latent score differences dž encode the graph structure and the observed score differences d' are generated using the inverse transform G
2. Score difference correlations: As shown in Lemma 2, the column space of the correlation matrix of the score differences contains crucial information about the latent graph and the inverse transform, which we will leverage form estimates for the latent graph G and the inverse transform G
To proceed, for m E [ri] we denote the correlation matrices of dx and d' by
R A Ex (x) (x)) and R - E (a) (x)))
(16)
Next, we formalize two critical properties of score differences and their correlation matrix. Specifi- cally, the following lemma states that the sparsity pattern of the latent score differences dž exposes the structure of the latent graph, and the observed score differences d% preserve this information through the pseudoinverse of G.
Lemma ([5]), Score function differences in the latent space satisfy, for all m E [n]]
Vz E IR:: (d (2)); = + E pa(I""..
(17)
Furthermore, the score differences in the observed domain are given by
(Gt) (z),
I G
(18)
The next lemma specifies that the structure of the column space of correlation matrix R is heavily constrained by the graph structure and the inverse transformation G
Lemma 2. For any m E [m]. we have col ( ))) C span {(G)) :.4 i pa(
While these two properties enable recovering the latent graph and variables, the ground truth score functions d (2) and correlation matrix R are unknown. We only have access to their noisy counterparts, as estimated from the observed data. In our algorithms, we use methods with soft decision rules that can counter the effects of the errors introduced by the score estimation procedure. These are facilitated by the following three key definitions.
5

---

Algorithm Causal order estimation
1: Input: RD for all m E [n]. ry 2 0
2: Vn f- [1, n
remaining unordered set
3: for tr (n..... 2) do
4:
for k Vi do
5:
if dim
R":") = =t then
6:
Te +
P _ has no ancestors in f > remove the identified node from unordered set
7:
Vi-1 V. {k}
8:
break & loop
9: t for m E V1
Return
Algorithm Graph estimation
Input: RT for all E [m], ग. 0, 0,720 00
2: Initialize & with empty graph over nodes { nn)
3: Construct the Vi sets of Algorithm I for all I. E [n] using
4: for I (n 1,...,1] do
5: for E (t 1, do
6:
Mr. + V3 ((TL) U cl.)))
for determining whether w. + n
7: if coll Rm;;) :n) 1, null(Emem, RT;")) then
8:
Add mee + T and n. + to 9 for E ch((T)) in
9: Return
Definition (Approximate column space). We define the n-approximate column space of a positive semidefinite matrix A E Rddd,, denoted by col(A; n). the span of the eigenvectors of A associated with the eigenvalues that are strictly greater than
Definition 4 (Approximate null space). We define the n-approximate null space of A, denoted by null(A; A)) the orthogonal complement of col( A;
Definition 5 (Approximate subspace orthogonality). We say two subspaces A Aand B with orthonormal bases A and B are 7-approximately orthogonal, denoted by A L., B, if B A S
In these definitions, setting 1 7 0 yields the standard definitions of column and null spaces and orthogonality. Next, we describe our algorithms for latent graph recovery (Algorithms and 2) and latent variables recovery (Algorithm 3). We note that the algorithms for latent graph and latent variable recovery algorithms are fully decoupled, enabling the independent recovery of the graph and the latent variables.
Algorithm Causal order estimation. In this algorithm, we estimate permutation и of [n] such that / o æ is a valid causal order. This serves as an intermediate step for estimating the latent graph. For this purpose, we use the noisy correlation matrices {R m E [n]] to identify the leaf nodes with no children. In particular, the key property is that when 1 is a leaf node, by carefully selecting the threshold 7,, the approximate column space of the term (Eme(x) R - R has dimension n 1. Precisely, with high probability, we have
dim col
Σ
R n) =n
1 leaf node.
(19)
After finding leaf node, we iteratively identify the youngest node among the remaining set of nodes. Leveraging this, we construct the permutation which consists of nodes ordered from the eldest to the youngest. In Lemma 3, we show that
a valid causal order with high probability.
Algorithm 2 Latent graph estimation. In Algorithm 2, we use the causal order found in Algo- rithm and correlation matrices (R m E [n]] to form graph estimate ś. We build this graph iteratively by considering a candidate edge स, - my for all possible (t,j) pairs starting from a leaf node t. The key property that we leverage is that we can form two subsets V, and Me, of [r] using

---

Algorithm 3 Inverse transform estimation
1: Input: R for all m E [n]. 17 2 0
2: H < Onxd
3: for (1, (1....,n)) do
4: C col"(((
5: H..: v for C and ||v|22
6: Return H
t, and such that, for sufficiently small y, with high probability the following approximation holds.
col Σ RT: Ly null RT:)
1 in G
(20)
meV,
mEMss
We check each edge Te + Ty and add the detected edges to the estimated graph G. In Theorem 1, we show that this procedure guarantees a PAC latent graph recovery.
Algorithm 3 - Inverse transform estimation. In Algorithm 3, we build our inverse transform es- timate H one row at a time. The key property we use is that for any m E [n] and unit vector E ()), the following error term is small with high probability
.
(v (vT. GG
(21)
AEPa(Im)
In other words T X is approximately equal to ZTT up to mixing with (Z, : : pa([")). which conforms to latent variables recovery objective. Note that in the noise-free setting, an exact equality holds due to Lemma 2 and property G = I,, Based on this observation, in our algorithm, we construct our inverse transform estimate by setting row m of H to unit vector E col(R for all m [n]. In Theorem 2, we show that Algorithm achieves PAC latent variables recovery.
5 Sample complexity analysis
In this section, we analyze the sample complexity of our CRL algorithm to establish an achievable sample complexity for CRL.
Threshold selection. A critical step in our algorithm designs is choosing thresholds and ? specified in Definitions 3-5. These thresholds determine the approximate ranks of noisy matrices and approximate orthogonality between subspaces, respectively. Specifically, we select 1) such that the approximate rank of R tracks that of R with high probability. To proceed, we denote the minimum nonzero eigenvalue among arbitrary Ry sums by
min min MCMm
{
Σ MEM
R
iE [d] X (E MEAM
R
R + #0).
(22)
where X(A) Rdd denotes the vector of eigenvalues of A. In our algorithms, we let E (0, and show that this choice ensures that eigenvalues of the null and column spaces can be separated via For the approximate orthogonality test in Definition 5, we show that 7" defined below serves bound on how close the non-orthogonal column spaces of R sums become orthogonal.
min G G /G..lll.-
(23)
Similarly, we let y E (0,7*) in our algorithms. For any choice of and y, we define min(n, n and 7, min(7, -3). We note that we do not have to know 17" and y priori, and can include routines to estimate them practice. These estimates do not have to be highly accurate since even rough estimates suffice to choose reliable thresholds 7 and y. Specifically, based on estimates for 17" and y", we can choose "safe" thresholds for 1 and 7, e.g., one-fourth of the estimates for 17" and y²,
that (i) with high probability we satisfy the requirement 7) (0, 17") and y E (0, )"). and (ii) we can avoid collecting excessive samples and compromising the sample complexity bounds. We provide the details of constructing such estimates of v) and > in Appendix G.
Sample complexity results. We provide two sets of sample complexity analyses for the latent graph and the latent variables. We estimate the latent graph in two steps: (i) causal order estimation
7

---

(Algorithm 1) and (ii) latent graph estimation (Algorithm 2). Algorithm I only employs approximate rank tests. Therefore, we first show that the approximate rank of the sum of correlation matrices {RX m E [n]} tracks that of {RX m E [n]} with high probability. To proceed, we define the following constants that appear repeatedly in our analysis:
3 (4 max me (m)
| ppx)
and
8mi 2 min |
(24)
mm(mn)
px
Lemma 3. Let E (0,7"). For any > 0, (o) samples suffice to ensure that with probability at least - 8,
W [n]
dimcol Σ
R
rank E
R
(25)
mEM
mEM
where
Nrank(0) (6) A N min
3n
Smin }.0)
(26)
Note that the function N(.,-) is an inherent property of the score difference estimator specified in (15), and it is monotonically decreasing in its second argument. Using this lemma, we show that Algorithm returns a permutation π such that π is a valid causal order with high probability.
Lemma 4. Let E n0, Under Assumption for any 8 O. No) samples suffice to ensure that with probability at least 1 - 8, I π is valid causal order, where is the output of Algorithm 1.
Next, we show that Algorithm 2 achieves latent graph recovery with high probability.
ni") and 7 E (0,7"). Under Assumption 1, for any 8 >> O, Ng(0) samples suffice to ensure that the output (xN)) collectively generated by Algorithms and satisfies 8-PAC graph recovery, where
Theorem 1 (Sample complexity Graph). Let 1j E (0,n")
37
Bm
3min }.0)
No( N min
(27)
2n
We note that constants 3 and Bmi are sample-independent. Then, (27) specifies the sample com- plexity function of the hyperparameters 1/, 7, target reliability 8 (0, 1), as well as the latent dimension n. Next, we state the complementary result for recovering the latent variables.
Theorem (Sample complexity Variables). Ler n E (0.n"). For any e > 0 and 8 > 0, Nz 8) samples suffice to ensure that the output H(Xx) of Algorithm satisfies (c,6))PAC causal variables recovery, where
Nz(e, 6) N min {
eßn, G/
By,, Pmin }. 6)
A
(28)
Theorems and collectively specify an extent of identifiability achievable in the sample regime. Importantly, we note that since we can establish (e, 6) identifiability guarantees for any vanishing c, using finite samples, Algorithms and are consistent estimators of the latent graph and the inverse transformation up to the corresponding equivalence classes.
Finally, note that the latent variables are recovered up to mixing with parents, as specified in Theorem 2. This result is a refinement of the existing latent variable recovery results under soft interventions in existing literature [5, 7], which recover the latent variables up mixing with ancestors.
RKHS-based score estimator. So far, we have characterized the sample complexity for any consistent score difference estimator. Next, we specialize the results by adopting the RKHS-based score estimator of [12]. We adopt this particular choice since it has known non-asymptotic sample complexity properties. To our knowledge, it is the only score estimator equipped with such a guarantee. To use the sample complexity of this score estimator in our paper, we first show that it is consistent in the sense of (15). For the formal statement of the following property and its attendant assumptions, we refer to Appendix E.
Lemma 5 (Informal). Assume that 8x and 8x satisfy the conditions of the RKHS-based score estimator in [/2]. Then, for any given 8 and e, the convergence specified in (15) holds when
C - N(ee 8) 2 "maa { 2)222))² (log
(8n)
(29)
8
8

---

8, and the latent dimension where &. and C are sample independent constants that depends only on Px, PX for m E [n] and the structure of the RKHS.
We use Lemma 5 to customize the general sample complexity bounds in Theorems and 2 to the RKHS-based score estimator. For this purpose, we first provide our sample complexity result for recovering the latent graph.
Theorem 3 (RKHS-ban based sample complexity -raah). Let n E (0, and Y E (0, Under Assumption and the conditions of Lemma 5, (g(8) samples suffice to ensure that ((NN) collectively generated by Algorithms I and 2 satisfies 8-PAC graph recovery, where
No(6) mmxx { C eg 2v2n2 22222))
log 8
8n )²²
and cg & min {
Bn- 3n-7-
Pmin
2n
(30)
Remark 1 BRKHS-basel error bound Graph). Theorem 3 implies that using N samples, the output (Xx) of Algorithms 1 and 2 satisfies (NV) graph recovery, where
C { C (V2222 })
6g(N) 8n exp exp
-N2/4
max
(31)
6g
Similarly, we leverage Lemma to specialize the general sample complexity in Theorem 2 to the RKHS-based score estimator.
Theorem 4 (RKHS-base sample complexity Variables), Let rj E (0, n)), Under the conditions of Lemma 5, (z(c, 8) samples suffice to ensure that the output H(xx) of Algorithm 3 satisfies (eAC causal variables recovery, where
Nz(e, = mmxx S C (..2)
( (log
8n 8m
))²
,2222
(32)
and
eB11. G
min
Br,, Pmin
(33)
We note that the results in Theorems and show more explicit dependence of the sample complexity the latent space dimension n. We observe that the sample complexity of latent graph recovery explicitly depends on and the latent dimension n according to O( (n log $)*). Similarly, the sample complexity of latent variables recovery explicitly depends
n according to O(( y log ))) We note that constants 3, 3mins 17",, and y are model parameters, and their scaling behavior in terms of n and d are investigated numerically in the next section.
6 Experiments
In this section, we perform numerical assessments of our analyses to provide complementary insight into the sample complexity results of Scction 5. Specifically, constants with respect to problem dimensions n and d. Furthermore, we also evaluate performance variations of the sample algorithm in terms of the variations in the score estimation error. For this purpose, we focus on the mean squared error (MSE) of the score estimator, specified by Elldk d I These evaluations facilitate better understanding of the properties of the CRL explicit in our theoretical queries.
evaluate the variations of the model
problem that
Experimental details. We consider problem dimensions n E (3, 5, 10) and E {n, 15) and generate G using Erdös-Rényi model with density 0.5 on nodes. We adopt linear Gaussian models as the latent causal model. We consider N E 210..5 103, 103.5 10 101.5 10$) samples, and generate 100 latent models for each triplet (N, d). We generate N samples of Z from each environment for each latent model. Transformation G E Rdxn is randomly sampled under full-rank and bounded condition number constraints, and the observed variables are generated as G Z. Due the Gaussian structure of Z, the observed variables X also have multivariate Gaussian distributions with
'The codebase for the experiments can be found at https://gitane com/ acarturkrttr..a
finite- sample-limeeeeeeeee linear-crl.

---

recoverry
0.75
n=
Constorta
10
0.50
10
0.00
10
Number of nodes
Score estimation MSE
Constants problem dimension.
(b) Graph recovery MSE, d = 15
Figure 1: Numerical evaluations.
score function 8x (x) O I, where θ the precision matrix of X, Therefore, we estimate 8x using the sample precision matrix estimated from N samples, θN as & (2; Xx)) Ô
Results. The sample complexity results depend on dimension and d through their explicit presence as well as their implicit effect on model-dependent constants 3, Amins 17,,, and y", as established in Theorems 1 and 2. First, we observe that all these parameters are independent of d. This is also expected theoretically since we can project down the dimensional observed space to the n dimensional (G). In Figure la, illustrate the dependence of these constants data dimensions and d. We observe that > remains constant, while 3 and Smin are decreasing n increases, but the decay is not steep. On the other hand, we observe that r7" decays exponentially with n. ?" is implicitly controlled by the condition number, which is kept bounded. We recall that 9min is the minimum among {||d Ilpx m E [n]], and similarly, 5 is the inverse of the maximum of {Ild* Px
E [n]] }. so they are expected to become smaller as increases. Finally, for 17", we note that the definition (22) is an order statistic among exponentially many, 2n, subsets.
Next, we note that all the imperfections in the graph and variable recovery are due to the imperfections in score estimates. In fact, this the bottleneck in our decisions: the key impact of finite samples versus infinite samples is the degradation in the quality of score estimates. To have a direct insight into how the score estimation noise power translates into decision imperfection, we assess the quality of graph recovery success rate versus varying degrees of mean score eπror of score difference estimates Eilldx d' 1 for different triplets (N, n, d). In Figure 1b, each data point corresponds different sample size N, and the legend entries {3, 5, 10} denote the latent dimension n. This figure illustrates the scatter plot the error probability 5 versus MSE for different parameter combinations and the corresponding local regression curves. It is observed that in the low MSE regime, 1 decays linearly with respect log E[[[dx is due to our algorithms' high sensitivity to errors in estimating approximate matrix ranks.
dxx || and plateaus as the MSE increases. This trend
7 Conclusion
In this paper, we have established the first sample complexity results for interventional causal representation learning. Specifically, we have characterized upper bounds on the sample complexity of latent graph and variables recovery in terms of the finite sample performance of any consistent score difference estimator. We have, furthermore, adopted particular score estimator [12] to derive explicit sample complexity statements.
Our sample complexity results are given for partial identifiability (up to ancestors) in the soft intervention and linear transformation setting. Establishing sample complexity results for perfect identifiability via hard interventions or considering general transformations are important future directions.
Acknowledgements and disclosure of funding
This work was supported by IBM through the IBM-Rensselaer Future of Computing Research Collaboration.
10

---

References
[1] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning, Proceedings of the IEEE, 109(5);612 634, May 2021.
[2] Aapo Hyvärinen and Petteri Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural Networks, 12(3):429-439 April 1999.
[3] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In Proc. International Conference on Machine Learning. Long Beach, CA, June 2019.
[4] Burak Vanieı Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning with interventions. urXiv:2301.08230, 2023.
[5] Burak Varieı, Emre Acartürk, Karthikeyan Shanmugam, Abhishek Kumar, and Ali Tajer. Score- based causal representation learning: Linear and general transformations. arXfv:2402.00849) 2024.
[6] Kartik Ahuja, Divyat Mahajan, Yixin Wang, and Yoshua Bengio. Interventional causal repre- sentation learning. In Proc. International Conference Machine Learning, Honolulu, Hawaii, July 2023.
[7] Chandler Squires, Anna Seigal, Salil S. Bhate, and Caroline Uhler. Linear causal disentangle- ment via interventions. In Proc. International Conference on Machine Learning, Honolulu, Hawaii, July 2023.
[8] Burak Varieı, Emre Acartürk, Karthikeyan Shanmugam, and Ali Tajer. General identifiability and achievability for causal representation learning. In Proc. International Conference on Artificial Intelligence and Statistics, Valencia, Spain, May 2024.
[9] Simon Buchholz, Goutham Rajendran, Elan Rosenfeld, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[10] Julius von Küg Kügelgen, Michel Besserve, Wendong Liang, Luigi Gresele, Armin Kekić, Elias Bareinboim, David M Blei, and Bernhard Schölkopf. Nonparametric identifiability of causal rep- resentations from unknown interventions. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[11] Jiaqi Zhang, Chandler Squires, Kristjan Greenewald, Akash Srivastava, Karthikeyan Shan- mugam, and Caroline Uhler. Identifiability guarantees for causal disentanglement from soft interventions. In Proc. Advances Neural Information Processing Systems, New Orleans, LA, December 2023.
[12] Yuhao Zhou, Jiaxin Shi, and Jun Zhu. Nonparametric score estimators. In Proc. International Conference on Machine Learning. virtual, July 2020.
[13] Jikai Jin and Vasilis Syrgkamis. Learning causal representations from general environments: Identifiability and intrinsic ambiguity. arXiv:2311.1226: 2023.
[14] Simon Bing, Urmi Ninad, Jonas Wahl, and Jakob Runge. Identifying linearly-mixed causal representations from multi-node interventions. In Proc. Causal Learning and Reasoning, pages 843-867, Los Angeles, CA. April 2024.
[15] Zhenyu Zhu, Francesco Locatello, and Volkan Cevher. Sample complexity bounds for score- matching: Causal discovery and generative modeling. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2023.
[16] Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4):695-709, July 2005.

---

[17] Yang Song, Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Proc. Uncertainty in Artificial Intelligence, virtual, August 2020.
[18] Andre Wibisono, Yihong Wu, and Kaylee Yingxi Yang. Optimal score estimation via empirical bayes smoothing. arXiv:2402.07747, 2024.
[19] Chandler Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. ii. SIAM Journal Numerical Analysis, 7(1):1-46, 1970.
12

---

Sample Complexity of Interventional Causal Representation Learning: Appendices
Table of Contents
A Proof structure
13
B Identifiability guarantees infinite sample regime
14
B.1
Proof Lemma
B.2
Encoder recovery
15
B.3 Equivalence of function rank to correlation rank
15
B.4 Causal order recovery
16
Graph recovery
C
Identifiability guarantees under bounded score estimation noise
19
D Sample complexity for generic consistent score estimator
25
E Sample complexity RKHS-based score estimator
27
F Properties of positive semidefinite matrices
28
G Hyperparameter estimation
29
A Proof structure
We structure the proofs of our main results as follows.
Appendix B Infinite sample guarantees: First, we prove identifiability results in the noise-free setting, that is, using the ground truth R matrices instead of using the estimated RT.. These intermediate results lay groundwork for the proofs for the finite sample setting.
Appendix C Bounded noise guarantees: Next, show that if estimation enror for the score difference functions, ||xx d llpx bounded, then the noise-free identifiability guarantees transfer to the noisy setting.
Appendix Sample complexity guarantees: We use the noisy identifiability guarantees to prove that for any consistent score difference estimator, we can guarantee (c, 5PAC guarantees for CRL identifiability objectives.
Appendix E RKHS-basen score estimator: Finally,
the finite sample guarantees provided by the RKHS- based score estimator of [12] to adapt the sample complexity statements for generic estimator to explicit guarantees in terms of model-dependent constants.
To be used throughout the proof, we define the correlation matrices of d
R
Epz do (z) (z)
(34)
We recall the correlation matrices R and RTT specified in (16). For subset M C [n], the following shorthand notations for sums of the matrices in {R m E MM and (R m M).
R
m
and
R
R
WA [n]
(35)
13

---

B Identifiability guarantees in infinite sample regime
In this section, we provide the identifiability guarantees of Algorithms 1-3 with no error and probability 1 when using { m E [n]] as input.
Denote the image of a function f: R" - R for any k E 2, by im()), that is,
im - {f(=)
R"
(36)
First, we note property of the column space of correlation matrices.
Lemma 6. For a continuous function f: R" + Rt, span of the image of f equals to
span im( col (Enz lf(=) [[(=
(37)
Proof: Note that two subspaces are equal and only if their orthogonal complements are equal. We denote the orthogonal complement of span im(f) by
S - (span im()) E y f()) =0 Vz E
(38)
The orthogonal complement of the column space of symmetric matrix is the null space, which denote by
S null (Epz)f(=) f(z) = fy e R Ep2(f(z) - --=)
(39)
Since any correlation matrix is positive semidefinite, using Proposition 2, (39) can be written as
S2 = ( : Y Epz(f(=) f2) y=
(40)
-E Fpp((y" f()))² 0
(41)
Since f is a continuous function, so is y f for any E R We can then use [5, Proposition 2]. which is stated below for the sake of conciseness.
Proposition ([5, Proposition 2)). Consider two continuous functions f.g : R2 RR Then, for any O,
a R" f(z) g(2)
Epz
-(2)) *0.
(42)
Under this proposition, (41) can be written
S f e R YT f(2)=0 =0 Vz E
(43)
which is the same as the definition of S; in (38). This concludes the proof.
Corollary 1. For continuous function f: Rd R the span the image of f G equals the column space of Ep 2) (f(G 2)) I = Epx [f(x) (f(x))
(44)
We can specialize this lemma for d and d for any m [n]. which yields
col ( = span d (2) 2 E R"). }
(45)
and
col [ span (x) col( }
(46)
B.1
Proof of Lemma 2
We can state (17) from Lemma equivalently as
Zz R (d)( #0 0 = i pa(("").
(47)
Recall from (18) in Lemma that d is related to d% by
(x) = (G d (2) = Σ (G (z)
x= G
(48)
(E(n]
14

---

Then, due to (47), for any given 2 E R" and corresponding r G 2, we have
(x
Σ
(Gt),, (d% (=)); span { (G 1. pa(
(49)
sEPal!m)
Since dx (x)
lies in the subspace span (pan((G)))) )a pa (TT) for any x col(G), have
span
dxx (x) E span { (G) ); pa(
(50)
Due to (46), we have
span { [x(()) E col } ()
(51)
which concludes the proof.
B.2 Encoder recovery
We can use Lemma 2 show that in the infinite sample regime, Algorithm works correctly. Specifically, let us show the following.
Lemma (Infinite samples Encoder). For any v E col(R we have
(v G), #0
i E pa(("").
(52)
Proof: Due to Lemma 2, for any v E (R)) we have
v E span
(G. : i pa(1"))
(53)
In other words, any v E col(R can be expressed as
Σ ((G
(54)
(Epa(1m))
for some constants {G : i E pa( [. Then, we have
G Σ Gs (G
G Σ a. (G G. kEpa(T"))
(55)
Since G has full column rank, the pseudoinverse G satisfies G G Ins that is,
(G* ) -G e
(56)
where denotes the i-th standard basis vector. Substituting this, (55) becomes
G
Σ C e
(57)
(EPA(
Note that i-th entry of a row vector w E R is given by w e, Therefore, we have
{ C; i pa("),
(v G)² (vT.G);
(58)
otherwise.
This concludes the proof.
B.3 Equivalence of function rank to correlation rank
In this section, we adapt the workhorse lemmas of [5] to our setting.
Lemma 8 ([5, Lemmas 5 and 6)). Consider A C [n] such that I (Im A) is ancestrally closed, iee. pa(Tá) = TA, Then,
rank R A
(59)
Also, under Assumption for any 1: A. have
[A| [A| -1
if 3j A (k) such that I pa([)),
rank (ank(RAA)1)))
(60)
otherwise.
15

---

We first note that due to (18) and the definitions of R and R in (16) and (34), we have
R ( R G!
(61)
where GT is full row rank matrix. Therefore, for any B _ [n].
rank (R = rank (R
(62)
Next, we note that for a function f: R" + B2 the notation R(f) in [5] is used to denote the "rank" of function, and corresponds dim span im( the notation of this paper. Using Proposition and Lemma 6, we can see that the notation RFF) for set of functions F can be given as
R(F) = k dim
N (span if))
(63)
FEF
k dim
n
null(Ep,
Ex px [f(2) f(2) TD)
(64)
fEF
k dim null(
Ep [[)) [(=)])
(65)
JEF
dim coll
Σ FEF
pp) [(=)]])
E
(66)
Using (66) and (62), can adopt [5, Lemmas 5 and 6] using (RT E [n]} matrices.
We note that (59) and (60) together with Lemma imply that, for any ancestrally closed A S [n]] and k E A for which there exists j A \ (k) such that 7 pa(T)), we have
col (R col R (M()) span (G 2. E pa(1~1)
(67)
We note that due to the property G R G In, we have, for any M S [n].
null (Gi)T 4. : i M span G..+ i M
(68)
and
null G. :E: = span (G i : i M)
(69)
B.4
Causal order recovery
We will show that Algorithm 1 gives valid causal order in the infinite sample regime using Lemma 8. Lemma 9 (Infinite samples - Causal order). Setting 77 = 0, 1 n is a valid causal order, where π is the output of Algorithu using {RT- m E [m]]-
Proof: The proof of this lemma follows closely to the proof of [5, Lemma 7J. Note that setting n means that approximate rank and column/null spaces are actually equal to the standard rank and column/null space definitions. We note that I o is a valid causal order if and only if, for any t [m]. we have
de([ S { I :i>t).
(70)
We prove (70) by induction as follows.
In the base case, for n, we have Vi = [m]. Therefore, using Lemma 8, we see that
rank(R VANK = { n de([*) n 14 + 0 n 11-1 de n 7V = 0
(71)
x
Therefore, for t n, rank R 1((1))
- 1 in Algorithm 1 if and only if k V. satisfies
0 = de 1 n n (e)) n [m] = do(T*).
(72)
Since (1 i () 0 for n, the base case is proved by choosing any such k: as ne.
For the induction step at time E (n 1, 1..... 1}. we assume that, for any u E [t+ 1I...... n) we have de( C 11. i > }. By construction. V. [r]] TT. > t}. Therefore, I is
16

---

ancestrally closed: For any & E I h cannot be descendant of [[m]] = { 1M u > { due to the induction hypothesis. In other words, pa(Ivi) I Therefore, we can use Lemma 8
rank(Rx X WARk) {
( t-1 do([²) 0 I 0 de([*) n I #
(73)
Therefore, for any t E {n 1..... satisfies
}. rank (ank (i((k)) ) =t - 1 in Algorithm and only if E V. 0 de( ) nive.
(74)
This is equivalent to
de( (T( S [n] \ =
= ( u> u>
(75)
Therefore, choosing any such as n, satisfies the induction hypothesis for t as well, and the proof by induction concluded.
B.5 Graph recovery
Lemma 10 (Infinite samples Graph), Setting -y = O, the collective output of Algorithms I and 2 using (R m [n]} is equal to the graph isomorphism of the transitive closure of g by permulation I.
The proof of this lemma follows closely to the proof of [5, Lemma 8]. Note that setting 1j = means that approximate ranks and column/null spaces equal to the standard definitions. Similarly, = means that approximate orthogonality is equivalent to the standard orthogonality definition. We first note that the transitive closure of two DAGS equal if and only if their transitive reductions are equal. Therefore, the lemma statement is equivalent to
Proof:
Ty E (
1 E (1
Vi,j E [m]
(76)
will prove this result by induction over the transitive reduction edges. the rest of the proof, using Lemma 9, we will leverage that I o is valid causal order.
In the base case, we have
and thus necessarily n. The only possible path between _ to In is therefore a transitive reduction edge. Since we did not add any children to node yet, the set Ma, equal to Vj \ {m.]. Noting that I''s ancestrally closed and the only possible child of T is 18 when T o is valid causal order, we can use Lemma 8 to obtain
rank Mud) X
{ n n-- Ins & ch(I")).
I ch((
(77)
Specifically, using (67), we can specify the exact column spaces we can obtain from Me. as
span { (G :iieee 1 span { (Gt) : iE MAMA)
1 E ch(l")), 1 & ch((
col RR
Mad)
(78)
Then, using (68), the null space of R May is given by
x
span { G. : P3
I ch(1 } th & ch(l
RR M
(79)
span G. : i MMMa)
The test in Algorithm 2 involves checking whether the column space of R and the null space of R MM are orthogonal. Note that 1% is ancestrally closed, therefore, using (67). we get
col(R kt span { (Gt) sa EE )) span { (Gt) :. i 1
(80)
Next, we note that the orthogonality test which uses orthonormal bases of subspaces (Definition 5) is equal to the following. Let A E Raxki and E Rd be full column rank matrices. Then,
col(A) 1 CBl = AA
B.....
B. B = =.
(81)
17

---

This holds since A At is the orthogonal projection operator onto (ol(A). Therefore, given or- thonormal bases Ag and By for A and B, we have A A A Ao and B B = Bo Bg Then,
AA
Ao Ag Bo B, | Boll2
(82)
which is precisely the metric used in Definition 5. To use this property, let us first consider the matrix G which is formed by stacking the independent column vectors in set {G.,i E A) for some subset S [n]. Since G has full column rank, we see that the pseudoinverse of G..A is exactly given by
(G..A)* (Gi)
(83)
where the matrix (GI) A.: Using this notation, we have
is formed by stacking the independent row vectors in set {(G) )i : i E A}.
( Mid) = span {GG!) : E (a
(84)
then the orthogonality metric is equal to
(G)))
a G Ne, G, pllpaaaees
G yintoniMesi
(85)
G., Gt me G (al G yontaamee
(86)
G.m Hoo, Gt poRmmess)
(87)
Σ
G. Glulll
(88)
SE/ SE/
Due to the construction of sets V/ and Maj. we have M MMss = 1 Therefore, the only entry in v that may be missing from pa MMa) is 1 Therefore, previous equation is equal to
( I G mr, G. G.nnnmmes Gt Jluroamess
(89)
- { [[ G lla ||G| melll2 1st & pa( Ma.)) 1 Me.))
(90)
In summary, (84) holds, the orthogonality inspected in Algorithm 2 happens if and only if 1 E pa(I-Mu:).
(91)
In the base case, since n 1, this holds if and only if T E pa,, (T%,), and the base case is done.
For the induction hypothesis, we assume that for any u E {n - I,...,& t + 1 }. all the transitive reductive edges has been correctly identified, that is, for any E [n]. Fu pa (m+) if and only TT E pa ): We show that the induction hypothesis is also satisfied for and j E [n] using induction on j.
In the base case, we have j = t+ 1. 1. This case works exactly the same way as the t t= n n-11 and = n case. For the induction hypothesis, assume that for any nn 1, ......j - 1,. all the transitive reductive edges between [dt and fT have been correctly identified, that is, n. E (T.) if and only if 7T pa,, (T*.). We prove that the hypothesis also holds for j as follows. First, that (((e))( is ancestrally closed set. Note that VV is ancestrally closed set by construction. Since the induction hypothesis ensures that all transitive reduction relations between = and l. for any E { 1,......,. ......,, 1) and i [n] are recovered, this also means that transitive closure relations, that is, descendants, are also recovered. Namely, the induction hypothesis implies
claim
(92) Next, the induction hypothesis for j implies that for any k E + 1 }, we have also identified all the transitive reductive edges = + _m Therefore, for Mr, ( V, \ ch(().) all the elements in ch(m)) has the property that their descendants have been fully identified, and therefore are excluded from the set (9 keeps the transitive closure), which means the set (mme) ancestrally closed. Since this set is ancestrally closed, have
1si E de( - n; E de(mu), Vu ( n 1}, Vi E [n].
M.M Mis U (
I & pa(I")), 1 E pa(
pa(T>Me.)=
(93)
18

---

or, using Lemma 8,
col (.)) span { (Gt) : : i pa(IM..)).
(94)
In the base case n, we had shown that this was a sufficient condition for ensuring that Algorithm detects the transitive reductive edges correctly. Therefore, we can detect any existing transitive reduction edges between 1 and 1n for any j and t, which concludes the proof.
C Identifiability guarantees under bounded score estimation noise
In this section, we show that as long as the error in the estimate of the score differences, maX ||dx dxIlpp is upper bounded by model-dependent constant, the results in the infinite data regime still hold.
The first key observation is that the error | R bounded in terms of ||xx d% lpx Lemma 11. In high signal-to-noise ratio regime for score differences, that is, when
dx - d |nx 2
||d px
(95)
the error in correlation matrix R is bounded by the error in dx as
R
S 4.
||
d d
(96)
Proof: First, note that
R R = Epx m (x)))
(97)
Px - - (10)
+ (x) ((x())))((()-)((0)))
(98)
+ (())
Next, we apply the spectral norm.
|
R 1|2
|| [1dx (x) dz()) (x))))((((())) -dx
dz(()) (dx d((x))
(99)
(dx))) dx))
S Epx [[dx (1) (x)) (dx (1l 2 ||x (x) (x) dx))))
(100)
Note that the first term the spectral norm of a covariance matrix, and is upper bounded by
||Ex [xdx(x) (x))) (xx dx (z)) "]1l, - Ep
- -
(101)
1 x px
(102)
For the second term, we can upper bound the spectral norm by Frobenius norm as Exx [d)(()
(dx(x) dx (x)) < Epx [x) df)
(103)
d
(Epx (d) - (f)()) (104)
=
Using inequality,
Exx [d) (ax (x) - <
Σ 1==
Epx (d)(())))) Epx (dx(xx) (<)(()))
(105)
Epx || (z) 11 Epx [xx(x) (1))
(106)
= -|d | || dx
1|
(107)
px
19

---

Therefore, we can upper bound || R 22 by
R R |dx dxx ppp +2
px -|dxx
dx px
(108)
Finally, we note that if (95) holds, then this bound simplifies to (96).
Our finite sample CRL algorithms use approximate column and null spaces of (sums of) noisy score difference correlation matrices Rx where M S [n]]. Therefore, we need to ensure that these approximate subspaces (i) have the same rank as, and (ii) are close to their noise-free counterparts.
First, show that under bounded score difference estimation noise, the approximate rank of R is equal the rank of R To show this, will leverage Weyl's inequality.
Lemma 12 (Weyl's inequality). For any two symmetric k x k real matrices A, B, we have
||^(A)= X(B) > A BB
(109)
where X(A) for symmetric matrix A denotes the vector of eigenvalues of A ordered in ascending order, and [/ is the maximum absolute value among the entries of v.
We can now show that the approximate rank of R matrices and sums are equal to the rank of R under proper threshold selection and low error.
Lemma 13. Define 1f" as the minimum nonzero eigenvalue among (R :M S [n]}, that is,
n"
- min min MCIn|
X (xx) E [d] X; R M) + 0
(110)
(i) For n E (0, if
max
R R 11 < min _n} = 17=
(111)
mEin
then, for any m E [n], we have
dim col (RT) dim col (Rx:")
(112)
iii) For (0, if
max mE(n]
R
me
// n2
(113)
then, any M S [n], we have
dim (R dim col R (R
(114)
Proof: Let us investigate the approximate rank of R under threshold 17 for any M S [m]. If the eigenvalues of Y that correspond to the cigenvalues of the null space of R are below the threshold 77, and the eigenvalues of R that correspond to the eigenvalues of the column space of R are above 7), then the approximate rank of R is equal to the rank of R Let denote the maximum amount any eigenvalue of R differs from the corresponding eigenvalue of R by
x A A A(R I
(115)
Thus, the eigenvalues of the noisy correlation matrix R that correspond to the null space eigenvalues of R is at most X. Similarly, eigenvalues of the noisy correlation matrix R that correspond to the column space eigenvalues of R is at least
min { A ( i [d]
X
(R
# #0} X.
(116)
Therefore, if
X イイくく < min A (
(d) X; +
(117)
then using threshold ensures that the approximate rank of R is equal to the rank of R We can generalize this statement as follows. First, note that, by definition,
n¹ min > (R ie [d] x (R 0)
(118)
20

---

Then, the rank statement about Rx is correct if X satisfies
x <nn X.
(119)
This statement can be equivalently written as
< min -1) 17.
(120)
Next, we find an upper bound on in terms of | - R |l using Weyl's inequality (Lemma 12).
x = |
< [ M R ll2
(121)
R X
R
(122)
mEM
[M|
max
R
(123)
mEIn
n max
R
R X
(124)
m
[n]
Therefore, for any E (0, (0,7"), leveraging the condition (120), we have
(i) If M| = and M = {m), we can use (123) to show that the condition
max
|R
x
R
< 1)+
(125)
me(n]
ensures that
dim col (Rx)
dim col (RT:")
(126)
iii) For any generic M, can use (124) to show that the condition
max mm[n]
R
R
7)
(127)
n
ensures that
dim col (RX) dim col (R :1)
(128)
This concludes the proof.
Since we have sufficient condition to ensure that approximate ranks of ( M C [n]] are equal to the ranks of (R-M .M S [m]], now we can state sufficient condition for finding valid causal order.
Lemma 14 (Bounded noise Causal order). Le (0, If
max mE(n]
Rmm
RT
7 n
(129)
then I o n. is a valid causal order, where n is the output of Algorithm 1.
We note that Algorithm I only uses approximate rank statements for (R . C [m]]- Therefore, the approximate rank statements are equal to the ranks of (RM M S [m]]. then, the infinite sample guarantees of Algorithm provided in Lemma 9 immediately transfer to the noisy R regime.
Proof:
Next, we note that Algorithms 2 and 3 use the direction information of the approximate column and null spaces of (R .M S [n]] well. Therefore, we need to bound the "distance" of the estimated subspaces from their noise-free counterparts. The main results we will use for this purpose are the Davis Kahan sin theorems [19], specialized for approximate column and null spaces.
Lemma 15 ([19, sin 0 theorem]). Consider two k i real symmetric matrices A and A. Denote the orthonormal bases of the column and null spaces of A by A1 and Ag. respectively, such that
A= C
(130)
where C₁ is symmetric matrix with the same eigenvalues as A. Similarly, denote the orthonormal bases for the approximate column and null space of A by Å and Åo, such that
A CO + A,
(131)
21

---

where eigenvalues of Co are that of the approximate mill space of A, and the eigenvalues of C₁ are that of the approximate column space of A. Define
x - min Amin (C1), Amin A (C1)-Amase )mn)
(132)
where Auax and Xuin denote the maximum and minimum eigenvalue of symmetric matrix. Then, given that the approximate rank of A is equal to the rank of A and O, we have
- - 11 All2
A
A
112
(133)
and
| Aoll2 - X
- All2-
(134)
Lemma 16 ([19, Symmetric sin theorem]). Under the setting described in the sin @ theorem above, we have
| AJ
Ao
AU
12
- - All2
(135)
and
A Al A
A
S 1 Al12-
1
(136)
We note that in these sin / theorems can be bounded using Weyl's inequality (Lemma 12) and the minimum nonzero eigenvalue of matrix as follows.
Amax (c)) S - 1l Amin (C1) Amin (C,) -
| Á A l12
(137)
Therefore,
2 min (C (CC)-|IA -
(138)
Using R for A and R for A, and using the definition of 17" in (110), we obtain
x x2 R R
(139)
In order ensure that the approximate rank of R&M is equal to the rank of R.M. it suffices that J R satisfies
7)
R M
R 11
(140)
due to (121). If this holds, we get
x> 17" 17. = (n, - 11} max 17" n} 2 min(n, 11" - 7} -7--
(141)
Therefore, the left-hand sides of (133)-(136) are upper bounded by
1
R M R
(142)
17.
We can use Karis-Kahaanna symmetric sin 9 theorem (Lemma 16) to prove that encoder estimation error is upper bounded by the error in R Lemma 17 (Bounded noise Encoder). Let v E (0, If (125) holds, then the output H of
Algorithm 3 satisfies
H- (Cpa + Car),
(143)
where for all @ pa(j). Cpa satisfies (Cpa)is and
||arrl12 - Vn ||G]] max mEIn]
R
R
(144)
Proof: We prove this result by considering each row m of H separately. Algorithm we select Hn, from (R) n) for each m E [n]. We start by noting that in Lemma 7, we have shown that using the noise-free score difference correlation matrices, we get
(v G), # i (a(
Vv col (R ||vl22 =
(145)
22

---

m. We can decompose any v E col(Rx: xx:0) as
7)
=u Ao v A1 A .v.
(146)
where Ao and A₁ are the orthonormal bases of the null and column spaces RX in line with the notation of the Davis-Kan Kahan sin 0 theorem. Note that A AT is the orthogonal projection operator onto the column space of RX therefore, using (145), we have
((A1 A v) G), #0
E pa(["))
e' col 2 =1
(147)
Therefore, the "erroneous" entries in v G can be written as
(v G..G., = -(Ao AT v) G);
vi & pa(?")), Vv E col(R || = 11
(148)
Note that if we choose E col(R (T) as of H, we have
(1 Corr) m,,12
Σ
(v G) 2 (| AD vv Gll2
(149)
Since v E Rx n). we have A AT v v. where Å₁ is the orthonormal basis of the
approximate column space of R.P. Using this and ||v||2 1, we can write (149) as
(P,, Carr) m,:l2 S AA A
v 1l2 ||G||2
(150)
Ao A
A A .v12
|G]||
(151)
5 Ao AJ
A A 1|, ||
(152)
= |A
Aill2
G GG 2'
(153)
Using Davis Kahan sin theorem (Lemma 15), when (125) holds, we can further upper bound the m-th row of the error term by
1 [ - RT ||G||2-
[I Cem) m. 12 <
(154)
7
Note that the spectral norm upper bounded by the Frobenius norm. Therefore,
Camllz I [Cerrlle S V 1.
max R R mEin]
(155)
77
Next, we investigate the approximate orthogonality test used for Algorithm 2 under noisy score difference correlation matrices.
Lemma 18. Let A, B, A, B be l x is symmetric matrices, such that
A A T A,CIAT,
À= A +ÁČČÁT B B + +BD,
(156)
B = B.D,B B,D,B
(157)
where [Ao, A1). [Bo, Bı). (Ao, A1). [Bo, Bi] are all k x l orthogonal matrices, and shapes of Au-Ao and Bu
Bu-Ba By match. Given that the spectra of (i) Co and Č₁ (ii) C₁ and Co. (iii) Dy and D1, and (iv) D2 and Do are all separated with gap X, we have
(i) 1f [[] Boll2 0, that is, if (col(A)) col(Bo), then,
AA Boll2 < X
(1 All2 +|2+ Blb))
(158)
(ii) DA Boll2 1 # O, that is, col(Ao) y col(Bo), then,
1 (
Boll, AJ Bo 112 2 k
A AIl + + B (1))
(159)
X
23

---

Proof: We first prove a perturbation bound on the product of orthogonal projectors.
|Ao
A
Bo
Bg
Ao
Ao BB B ll2
(160)
| Ag
(Bu-
B B,
BB) Bo.B,
(Ao
A - Aa - BB BB ll
(161)
< |A Aol
112
||B B - Bo B 1111 + AA AJ
Ao
A 2 |Bo
B ll2
(162)
$ |Bo BJ B. Bg 12 +|A Ag oo A ll2
(163)
Using Davis Kahan symmetric / theorem (Lemma 16) yields
Davis-Kahan
1 (1 A [|B-BB|]]
A A Bo
B. Au A B. BB 1l2
(164)
X
We use this result in separate cases: col( An) col( and col (An) YL col(
Case 1: (A)( 1 (B)). In this case, (164) immediately yields (158).
(ii) Case 2: col(Ag) y (B.). Let us define |A Boll2 = μ + 0. We can use (164) and triangle
inequality to get
|| A A
Bg B 11 +
( A l + | BBll)
(165)
X
A A Bo B
A Ag Bu B. Au Ag Bo B ll
(166)
2 Ao A Bo B
(167)
A Boll2 = μ
(168)
Rearranging the terms yields (159).
Finally, we show that the graph estimation is correct under bounded noise. Lemma 19 (Bounded noise Graph). Let 17 (0, and E (0,,"), where
min ME(n]
G. (G''). and T 2 mint7, 7 -7.
(169)
Under Assumption 1, the output & Algorithm 2 is the graph isomorphism of the transitive closure of the true latent graph G if
max mEin
R R
min
7+
(170)
n
2n
Proof: Algorithm 2 uses approximate column and null spaces of R for different M S [n]. Therefore, the generic sufficient condition (113), that is,
R R 7 n
max mE (1]
(171)
ensures that the approximate ranks of all R. matrices investigated in the algorithm will be equal to the rank of R To ensure that the estimated graph will be correct, we must guarantee that the approximate orthogonality tests will also give correct results. Using Lemma 18, we can show that the test metric is upper bounded in terms of maxme(n) | RT We do so by setting A R
Á = R B Rx and By as the null space of B. As shown in (141), (113) ensures that the spectral gap X in Lemma 18 statement is at least x > T7. In Lemma 10, we show that in the infinite sample, noise-fre freeeffre regime, when investigating (t. (). the test metric is given by
Mr., B- = Rx M
; and Ao as the orthonormal basis of the column space of A,
T- { [| (GGg)e)ll 1' pepe
| Bo 1
(172)
Since the approximate orthogonality test needs to distinguish even the weakest instance of non- orthogonality from orthogonality, we define
7" min || GG, [|GG)...ll> 1Emm
(173)
24

---

Using Lemma 18, we see that for (t,j) for which I' - 1 exists in G, if (113) holds, then
2n
| Bollz
max mein]
|
R
(174)
1/
Similarly, for (t, for which 1º + 1 does not exist in G, if (113) holds, then
2n
|| Bo B >
max mEin
R R
Rxl12
(175)
Therefore, for a choice of y (0,7*) ) to yield correct orthogonality decisions, suffices that
2n
2n T/e
R x
R
<TS
R R 1
(176)
mEin]
mEin
or, equivalently,
2n max mEnn]
R
RX min no.
(177)
T/
In other words, when using 7 E (0,77 7-) as the approximate orthogonality threshold, we can correctly identify orthogonal subspaces from non-orthogonal ones when
max P
R - R
7/7-
(178)
2n
Due to Lemma 10, all the approximate rank and orthogonality tests are correct, then the output ç of Algorithm 2 is the graph isomorphism of the transitive closure of the true latent graph G.
D Sample complexity for generic consistent score estimator
In this section, we will transform the bounded noise identifiability guarantees in Appendix C to sample complexity statements about generic consistent score difference estimator. Specifically, recall the consistent score difference estimator model from (15).
max mEin)
(xx
dx
px Se
2 1 8,
AA 2 ((e,8).
(179)
Recall the definitions of the constants in (24),
B
A
4 max
d
and
Bmin A 2 min |
(180)
mein]
px
mein]
px
First, we derive the sufficient samples for (e, 8) approoxxiig R using Lemma 11. Lemma 20. For any e and O, using Nn(c. 8) samples suffice to ensure that
P
max me/n]
R x
Rm
sc) 21 21-6 VA 2 Nn(e,
(181)
where
NR(e. 8) N (minfe- B, Bmin } 8)
(182)
Proof: In Lemma 11, in order to bound the error in R& for specific E [n]], we require
m dx
< 2. dx pxppx
(183)
px
To ensure this for all m [n), suffices that
max
|
2 min
d
8min
(184)
me/n]
mc|n]
Px
Under this condition, Lemma 11 shows that the error in correlation matrices Rg is bounded by the error in d& as
R
R
S 4.
|dx
1|dx
d plpx
(1855
25

---

To get an m-agnostic bound, we can take max of both sides to get
max
|
R
< 4- max
dx
max
m dx
dx
(186)
mein]
px
mEin]
px
In other words, to achieve error in estimating Ry, the error in estimating d'X suffices to be upper bounded by
6 _
max me(ni
||dx dx ll
(187)
maxmeln]
In summary, (184) and (187) together gives that
max mE(n]
dx
dx
min {mmino 33
(188)
Px
suffices to ensure
max
R
R 11 Se
(189)
mE
mm Using the sample complexity of dx. this means that
N Nn(c, 8) A N (min {c B, ): 6)
(190)
samples suffice to ensure this error upper bound on Ry with probability least 1 8.
Next, we restate and prove the sample complexity of estimating the causal order Lemma
Lemma 4 (Sample complexity Causal order). Let 17 E (.))))) Under Assumption I, for any 5 > O, Nrank (6) samples suffice ensure that with probability least 8, I o valid causal order, where a is the output of Algorithm 1, where
Amin ).
Nrank (6) N
mminn
(191)
Proof: Lemma 14 states that long R& error is upper bounded by Re the output of Algorithm 1 correct. Then, using Lemma 20, we see that
2
NR
7 8) =
min
Bm. ,,))
Amin
(192)
n
samples suffice to ensure that the estimated causal order is correct with probability at least - 5.
Next, we prove the sample complexity of estimating the latent graph.
Theorem (Sample complexity Graph). Let v E (0, and y E (0, Under Assumption 1, for any > 0, (ō( samples suffice to ensure that collective output (XNN) of Algorithms and satisfies 8-PAC graph recovery, where
(min
31. n
Bm-
3mim)
No( e N [in
(193)
2n
Proof: Lemma 19 states that the estimated graph is correct
max mEIn
R
R
< min
?) 7/
(194)
2n
Therefore, Lemma 20 implies that
fn- BT,
}.0)
N 2
N
min
Pmin j.
(195)
n
2n
samples suffice for correct graph recovery with probability at least 8. 8. Similarly, we prove the sample complexity of estimating the causal variables.
Theorem 2 (Sample complexity Variables). Let 17 E (0) For any >> 0 and 8 > 0, N2 8) samples suffice ensure that the output H(Xx) of Algorithm satisfies (c, PPAC causal variables recovery, where
eBn.
3m.. Smin }. 6)
Nz(e, 5) 2 N min
(196)
VTil G
26

---

Proof:
Lemma 17 states that if the input enror is bounded by
max mE
R
R < 7
(197)
then the estimated encoder achieves error rate
|| 122 - Vn _
G|||
max mEin
R
R Se.
(198)
7/+
Therefore, to ensure (e, - causal variables recovery, it suffices that, with probability at least 1 - 6, the input error on R is upper bounded by
mEin!
max
R
R 22
min
[vnl GIle
T-
n7
(199)
Using Lemma 20, this implies that
eBn Vn G
Byn Buin }.
N N
min
(200)
samples suffice for ( causal variables recovery.
E Sample complexity for RKHS-based score estimator
In this section, we adopt the RKHS-based score estimator of [12], state its assumptions, derive its noise model for score difference estimation, and use this model to make the sample complexity upper bounds derived in Appendix D explicit.
The score estimator in [12] requires the support of the distribution to be an open subset of its domain [12, Assumption B.1]. Therefore, we estimate the score function of X through its orthogonal projection to the dimensional support manifold col G). The projection matrix can be constructed from observed data samples with probability long as N n.
Next, we state Lemma 5 formally including all the assumptions required.
Lemma 5 (Formal). Denote trace-class matrix-valued kernel by K:: IR IR - Raxd denote its associated RKHS by Hx, and define suprecol(G) trK((x,)) x). Define an integral operator on HK. as
Tx & (()-))(())))d {
E
(201)
where is is pdf. Assume that there exists f E HK and pm E for all m E [n] such that 8x = Lx.px f and s L Then, using Tikhonov regularization, under [12, Assumptions B.1- B.51, for any m E [nr for any ò E (0,1) and N 2 (2v2x² log 8n/5), with probability at least 1 6, score estimator in [12, Theorem B.1] satisfies
max me(n|
dx px SC. 80/8
(202)
where C' is a sample independent constant that depends only on px. px for m E [n]] and the structure Hy..
Proof:
We use the fact that for a function f E Hx, we have
||
|L.px fl - Lxxpx llap || l
(203)
Therefore, even if we estimate s using data from px but evaluate it on data from px. we can still bound the MSE of the estimate using the Hilbert norm. The result states that the Hilbert norm error bound is, for any E {0} U [n], and if N 2 (2v2x² log 4/8)4,
PP |158 S l C 1/4 log
2 1 2-18
(204)
Since ||. I1xx is a norm, we have
|dxx m dx llxx < |18 8x Ilxx + -xxlxxxlmx < 1x (1187 - - 8 + 1 - - 6xl1
(205)
27

---

Combining with the Hilbert norm error bound, taking union bound and defining C _ 2C11 loop we get
4
P
|
d'
1/4 .lgg 8)
2 10--2. 28
(206)
Note that the noise model in (15) requires bound maxme(n) bound, we get
|dx xxllxx px- By taking union
max mE(n
t |dx
dxilxx S N-144 log
2 2nd.
(207)
By replacing 5 with 8/2n, we get, when N 2 (2v2k22 log 8n/8)
8n
P
max mE(n
||dx m dx C NN-14
1/4 log
8
2 1 1,
(208)
which concludes the proof.
Corollary 2. The error bound given in this result can be immediately transformed into sample complexity statement. Specifically,
max mE/ni [n]
[xx
dx
50 21-11 NA N(e,))
(209)
where
8n 4 N(e, maxx 2222x² -))²² (log
(210)
Using this N(.,)) ) function, immediately make the sample complexity results in the previous section explicit. The theorem statements are also stated here for completeness.
Theorem 3 (RKHS- sample complexity Graph). Let (0,n")) and E (0,r²). Under Assumption I and the conditions of Lemma 5, N6(6) samples sufficient to ensure that the collective output (xxx) of Algorithms I and 2 satisfies 8-PAC graph recovery, where
No(() maxx { cg
2V2x2 2v2x²))
8n 4 log
))²
Bmz n
Bm- T
8
and Eg 2 min
Bmin
2n
(211)
Theorem 4 (RKHS- based sample complexity Variables). Ler E (0, Under the conditions of Lemma 5, N2 (e, 5) samples ensure that the output H(Nx) of Algorithm 3 satisfies (c, PAC causal variables recovery, where
Nz(E, |max (
C -_ 222222)
1)²
log
8n 8
))
(212)
(.17
and
eBm1,
6% min
Bi,, Priin
(213)
/nl G
Properties of positive semidefinite matrices
In this section, present properties of positive semidefinite (PSD) matrices that commonly used in our proofs.
Proposition 2. For a real x PSD matrix A. the mull space of A can be specified using the quadratic form as
null A) ( vvvv = Av
0}
(214)
Proof: For a vector v E R& Av = 0 implies v T Av unconditionally. We prove the reverse direction by showing that Av * implies v Av & 0. First, since A is PSD, it has Cholesky
decomposition A U U for some matrix E R If Av = U Uv of then Uv * 0. This implies v Av | * 0. This concludes the proof.
28

---

Proposition 3. If A, B are real l x k PSD matrices, then
null(A A + B) = (A) n n)))
(215)
and
col(A B) col(A) + col(B),
(216)
where + denotes the Minkowski sum between sets, which is defined, for any two subsets A and B of vector space, as
B
A, b
(217)
Proof: Using Proposition 2, we write null(A) (A + B) as
null(A B) E
(A + Bjv = 0}
(218)
Since A and B are both PSD, for any E R we have v Av 2 0 and v Bv 2 0. Therefore, v( B)v 0 holds if and only if v Av and Bv 0. That is,
null A + B) {v EvE R v Av A Bv = =
(219)
We note that, due to Proposition 2, the right hand side of this expression is equal to which concludes the proof for (215).
Next, note that the column space of a symmetric matrix is the orthogonal complement of its null space. Then, using (215), we have
col(A A + B) = (Aull(A + B)) = (null( A) n nB)
(220)
Since null(A) and null(B) are subspaces of finite dimensional vector space, we have
(null(A) n nul)(B)) null(A)* null(B)+ col(A) col(B).
(221)
This concludes the proof for (216).
G Hyperparameter estimation
In this section, we provide minor modifications to our algorithms that enable constructing rough estimates for threshold upper bounds '/ and y" in practice.
Estimating 1/" We note that Algorithm at step 4, matrices investigated must have either rank t cquivalently we have 2 37". This observation lets us itcratively build and refine an upper bound on 17" during Algorithm which and 3. For Algorithm itself, at time f, we can pick k E V2 with minimal f-th eigenvalue- -tis is threshold-free way of estimating the causal order.
1. Therefore. the 1-th cigenvalues of all of these matrices non-zero, or
use surrogate of 17" in the subsequent Algorithm
Estimating 7* We first note that definition in (23) depends entirely on the ground truth decoder matrix G and its pseudoinverse. Secondly, we note that Algorithm 3 can be used independently of Algorithm 2 to generate an estimate H of G1 up some estimation error and possible mixing among rows. We can compute the value
min H
H
(222)
kE(x)
which would be equal to y had H G and use it as our estimate of y
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sections 4 and 5 establish the results claimed in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the work, e.g., linear transformations, are clarified through- out the paper and discussed in Section 7.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

The assumptions for the theoretical results are clearly given in the theorem statements, and the proofs of the results are provided in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The algorithm details are described Section 4. The experimental procedure is described in Section 6. The codebase for the experiments can be found at https: / //gittub.cco com aaaaturk-ee saaeeessaalleeeeeeee winellleeieeerrcrre
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
31

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The codebase for the experiments can be found https: com/ acarturk-e/ feititteeeeiiieeeeeeeeeeeeeeeeee sample- leteee--ieerrcrre crl.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / httppsscccppbccccccceecce httpllic/iiieeeee Codeeubbm ssi aasonnooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental procedure described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The only experimental result with error bars Figure la. in which the 95% error bars reported but indistinguishable from the plot lines.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments are run on a single commercial laptop CPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nee///nsusseeeeeeeeeeeeeee cc ctte/pullcc/eeee de ines?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that the research in this paper conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical and does not pose potential negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
33

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is mostly theoretical and does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Portions of the publicly available code of [5], available under Apache 2.0 license, is adopted in the code of our experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
34

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The codebase for the experiments be found https: //gg:/hb//ttbbbb com/ acarturk-e/ faieetefiiiiieeeeeeeeeeeeeeeeeee sample- iinerr--ieee crl, and is released under Apache 2.0 license.
Guidelines:
The answer NA means that the paper does not release assets. Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
35

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "0uxPDmh1nn", "reviewer": "Reviewer_Yb2M", "summary": "This paper provides finite sample analysis for causal representation learning with general latent causal models, single-node soft interventions, and linear mixing functions. Sample complexity for identifying graphs up to ancestors and identifying latent variables up to mixing with parent variables have been studied.", "questions": "1. How to make sure that all the imperfections in the experiments are due to score estimates?\n\n2. Are there any intuitive ideas to extend the range of the finite sample analysis to more general settings in CRL?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, this is the first finite sample analysis for interventional CRL, which is a very interesting problem with high practical value.\n\n2. All theoretical results including definitions are organized clearly.", "weaknesses": "1. The considered CRL setting is a little bit restrictive compared to the recent ones. Specifically, the assumption of linear mixing function may restrict its usage in a lot of real-world scenarios. Meanwhile, the indeterminacy is non-trivial, and further process/disentanglement might still be needed. However, it is understandable since sample complexity might be much more difficult to get for more general models.\n\n2. Perhaps it would be better if there was more discussion on the assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our results interesting and the thoughtful questions. We address the questions as follows.\n\n- **Source of error in experiments.** \nTo assess the source of errors in experiments, we have the following analysis: In Appendix B, we establish the identifiability guarantees under the infinite-sample (i.e., perfect scores) regime. To verify this, we perform experiments using ground truth score functions. In these experiments, the graph estimation results were perfectly accurate in 100 runs, which implies that the graph errors we report in the paper are due to score estimation. We will add these perfect score results to the paper. To replicate these experiments with ground truth score functions, one can set the `estimate_score_fn` flag in `finite_sample_test.py` file line 57 to `False` and run the file.\n\n- **Intuitions for finite sample analysis for general CRL.** In this paper, we have shown that some critical decision problems relevant to CRL – such as edge detection – can be done\nvia soft decisions in a way that is amenable to error analysis. While the specific tools used (e.g., subspace estimation) were limited to CRL under linear transformations, we believe that the overarching approach of reducing CRL to soft decisions and then obtaining finite sample guarantees of each such step is a good starting point for designing and analyzing more general CRL algorithms.", "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": "", "extra_scores": {}}, {"review_id": "JdH9MDmXNU", "reviewer": "Reviewer_jaoy", "summary": "This paper provides finite-sample identifiability results for recovering the latent causal graph and the generating latent variables given observations in a high-dimensional space that have been generated by the latent variables by a linear transformation and single-node soft interventional data with interventions on all nodes. Previous work provides identifiability results only in the infinite-sample regime. The algorithms rely on score-based estimators which have been studied in literature. Specifically the correlation matrix of the score differences are shown to be constrained by the graph and the linear transformation matrix. To recover the graph, first a topological order on the variables is estimated. Verifying whether a particular edge exists is checked by a necessary and sufficient condition on the approximate orthogonality of the column space and null space. For the variables recovery, it is sufficient to consider a unit vector in the column space. An existing RKHS-based score estimator is used to obtain the final sample-complexity results.", "questions": "Please refer to the weakness section for major issues. A few miscellanous points:\n1) I haven't checked the details but it struck me as weird to notice that there is a specific value of \\gamma in (20) that verifies whether an edge exists or not. Is there any intuition for this? \n2) Typos - (22) M \\subseteq [n], Line 179. \n3) In Figure 1b, is there a reason why even for better score estimates, there is no point for the 10 nodes case?", "limitations": "Implicitly addressed in the conclusions.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Causal representation learning is an active field of study and theoretical work that provides finite-sample identifiability results is quite relevant in practice and of interest to the community. Overall the paper is well-written with a clear flow of ideas that makes it easy to follow. \n\nI liked that the proposed method has a decoupling between the score estimators and the rest of the algorithms with proofs for the infinite-sample regime separate. This helps us to understand that the difference in quality of finite-sample data versus infinite sample data is the score-estimators.", "weaknesses": "A few weaknesses (with the major one being point 1) follow:\n\n1. A major confusion for me was that the setting of the thresholds was not clear. If the true scores are not known, then how is \\eta set from \\eta* which depends on the unknown true score estimates. Similarly for \\gamma that depends on \\gamma^* that depends on the true transformation matrix. What am I missing? \n\n2. Overall, the paper has multiple instances of notations not defined which make the paper difficult to parse. For example, Definition 2 has P_I, C_{pa}'s diagonal entries undefined? Lemma 2 has the pseudoinverse subscript undefined. \n\n3. I also think that the experimental section needs basic details. One suggestion would be to cut out the final RKHS sample complexity bounds that are just plugging (29) into Theorem 1 and 2. \n\n4. The proofs in the paper first derive results for the infinite-sample regime where score estimates are error-free. Finite-sample guarantees are then obtained by bounding the error in the score estimates. It would make the paper stronger if the infinite-sample regime results are compared with existing work. \n\n5. In Figure 1b, why are there spikes in the recovery rate even for worse score estimate MSE? Does this go against the main message of the paper that worse score estimates should imply poorer graph recovery and latent variable estimation? \n\n6. What is the reason behind defining the variables recovery as it is defined in Definition 2. Is there a previous instance of such a definition because this doesn't seem standard. Any rationale would help the reader.\n\nOverall, I think the paper is a solid contribution if these questions are clarified. But my current score can't improve given these questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough review and thoughtful questions. We hope our answers address the main concerns of the reviewer. \n\n**Setting the thresholds.** We are grateful for the reviewer bringing this up. We recognize that our choices of thresholds could have been presented differently and in a significantly more general way. As the reviewer correctly points out, the current theorem statements are given for specific choice of thresholds that require the knowledge of unknown model parameters. However, this is **not necessary** for our analysis – it suffices to choose $\\eta\\in (0,\\eta^*)$ and $\\gamma\\in(0,\\gamma^*)$, which results in similar sample complexity bounds that depend on the thresholds $\\eta$ and $\\gamma$ directly. We will modify our theorem statements to make them clear. Let us explain why this choice suffices. \n\n- We prove our sample complexity results by deriving sufficient upper bounds on the score estimation noise for our thresholded approximate tests to succeed. We use two tests: a) An approximate rank test with soft threshold $\\eta$ that uses Weyl’s inequality for the analysis and b) An approximate subspace orthogonality test with soft threshold $\\gamma$ that uses Davis Kahan (symmetric) sin $\\Theta$ theorem for analysis.\n\n- In both cases, the approximate test uses a metric $\\chi$ to distinguish between two models, one where the noise-free metric value is $\\chi = 0$ vs the one where it is at least $\\chi\\geq\\eta^*$ (or $\\gamma^*$). In order to guarantee the correct output using a threshold $\\eta$ (or $\\gamma$), we must ensure that maximal error $\\Delta$ for the metric $\\chi$ satisfies $\\Delta\\leq\\min\\\\{\\eta,\\eta^*-\\eta\\\\}$ (similarly for $\\gamma$). Sample complexity results directly follow from these upper bounds on $\\Delta$.\n\n- For implementation purposes, this means that we can select $\\eta$ and $\\gamma$ arbitrarily small. We highlight that requiring hyperparameters (i.e., $\\eta$ and $\\gamma$) to be restricted in an interval determined by unknown model parameters (i.e., $\\eta^*$ and $\\gamma^*$ in our algorithm) is standard (and generally inevitable) in the analysis of regularized algorithms in high dimensional statistics for even simpler problems like sparse support recovery. A common example is the error bound for regularized lasso problem in [HTW, Theorem 11.1], which requires the regularization parameter $\\lambda_N$ to be greater than $2\\\\|{\\bf X}^\\top{\\bf w}\\\\|_{\\infty}/N$ – which depends on the _noise realizations_ $\\bf w$.\n\n[HTW] T.Hastie, R.Tibshirani, and M.Wainwright. Statistical learning with sparsity. _Monographs on statistics and applied probability_, 143, 2015.\n\n**Experiment details.** The experimental details are currently provided in Appendix G. We will add those details to the main paper by using the additional page that we can have in the final version.\n\nWe also note that Theorems 3 and 4 are essential in the main body. It’s correct that the main results are Theorems 1 and 2, yet they are implicit in the sample complexity of a score estimator. We believe that having Theorems 3 and 4 explicitly is essential for accessibility.\n\n**Experiment results.** Each data point in Figure 1b corresponds to a specific $(N,n,d)$ tuple (listed in Appendix G). Importantly, for each $(N, n)$, the current plot includes two $d$ values: $n$ and 15. In x axis of Figure 1b, we erroneously plotted the MSE divided by $d$, which resulted in a plot that is the union of two shifted monotonic graphs for each $n$. We have corrected this error in Figure 1 of the PDF attached to the global response and presented the results in two figures accordingly. The new plot shows the desired monotonic behavior without major performance spikes.\n\nIn the same new plot, we also added a data point for a larger number of samples to show that a good graph recovery rate is possible for latent dimension $n=10$.\n\n**Infinite sample results.** Thanks for the suggestion. We will add the following theorem (and its latent variables recovery counterpart), along with the attendant discussion, to the main paper.\n\n_**Theorem (Infinite samples – Graph).**\nIn the infinite sample regime, under Assumption 1, for any $\\eta\\in(0,\\eta^*)$ and $\\gamma\\in(0,\\gamma^*)$, the collective output $\\hat{\\mathcal{G}}$ of Algorithms 1 and 2 is the graph isomorphism of the transitive closure of the true latent graph $\\mathcal{G}$._\n\n**Latent variable recovery definition.**  In the interventional CRL literature under linear transforms, two types of results exist. First, the so-called “perfect recovery” in which the latent variables are recovered up to permutations and scaling, which is defined exactly in the manner of our Definition 2 with ${\\bf C}\\_{\\rm err} = 0$ and ${\\bf C}\\_{\\rm pa}$ being a diagonal matrix, e.g., Definition 4 in [4]; Theorem 5.3 in [5]; Definition 1 in [9]. Secondly, the recovered latent variables are linear functions of some other variables as well. This recovery class is natural since Theorem 6 of [11] shows that element-wise latent variable identifiability is _impossible_ under soft interventions. Then, the various identifiability classes are defined similarly to Definition 2, e.g., Definition 5 in [4]. In these definitions, off-diagonal support of the recovery matrices (e.g.,  ${\\bf C}\\_{\\rm pa}$) denotes the mixing with other random variables that vary under different results, e.g., we consider “mixing up to parents” whereas [3] and [4] consider up to “mixing with ancestors”. \n\n**Notations and typos.** We thank the reviewer for pointing out several issues regarding notations and typos. ${\\bf P}_I$ is the permutation matrix corresponding to $I$, the intervention order. We will carefully fix the other under-explained notations and correct the typos in the revised paper.", "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": "", "extra_scores": {}}, {"review_id": "xt2xi1k109", "reviewer": "Reviewer_Q5cw", "summary": "This paper establishes finite sample guarantees for recovering the latent causal graph under stochastic soft interventions and observations under a unknown linear transformation. Experiments are conducted and code is given.", "questions": "- What is $P_I$ in equation (12)?\n- In practice, do we need to know $\\eta^*$ or $\\gamma^*$ to invoke your results? How do we know enough samples have been collected?", "limitations": "Nil", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well motivated and the contributions are clear.", "weaknesses": "I did not check the proofs in detail but I do not spot any glaring weaknesses.\n\nThe experiments are rather small scale (up to 10 nodes).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind review and thoughtful questions.\n\n- ${\\bf P}_I$ is the permutation matrix for permutation $I$, the intervention order. We will include the definition in the notations paragraph.\n\n-  The current theorem statements are given for specific choice of thresholds that require the knowledge of unknown model parameters. However, this is **not necessary** for our analysis – it suffices to choose $\\eta\\in(0,\\eta^*)$ and $\\gamma\\in(0,\\gamma^*)$, which results in similar sample complexity bounds that depend on the thresholds $\\eta$ and $\\gamma$ directly. Since this flexibility is critical for the practicality of our results, we will modify our theorem statements to make them clear. We emphasize that the changes to the proofs and the results are minuscule: it suffices to replace all occurrences of $\\eta^*/2$ and $\\gamma^*/2$ in our sample complexity statements with $\\min\\\\\\{\\eta,\\eta^*-\\eta\\\\\\}$ and $\\min\\\\\\{\\gamma,\\gamma^*-\\gamma\\\\\\}$, respectively. For details, please see our response to reviewer jaoy on “Setting thresholds”.\n\n- For implementation purposes, this means that we can select $\\eta$ and $\\gamma$ arbitrarily small. We highlight that requiring hyperparameters (i.e., $\\eta$ and $\\gamma$) to be restricted in an interval determined by unknown model parameters (i.e., $\\eta^*$ and $\\gamma^*$ in our algorithm) is standard (and generally inevitable) in the analysis of regularized algorithms in high dimensional statistics for even simpler problems like sparse support recovery. A common example is the error bound for regularized lasso problem in [HTW, Theorem 11.1], which requires the regularization parameter $\\lambda_N$ to be greater than $2\\\\|{\\bf X}^\\top{\\bf w}\\\\|_{\\infty}/N$ – which depends on the _noise realizations_ ${\\bf w}$.\n\n[HTW] T.Hastie, R.Tibshirani, and M.Wainwright. Statistical learning with sparsity. _Monographs on statistics and applied probability_, 143, 2015.\n\n- *Number of latent nodes*: We kindly note that the existing interventional CRL literature generally works with small graphs: $n=10$ is the largest graph size considered in the closely related single-node interventional CRL literature (e.g., for linear transformations [6] considers 5 nodes, [4] considers 8 nodes, and [11] considers 10 nodes. For linear causal models under nonlinear mixing Buchholz et al. (2023) consider 5 nodes. For fully nonparametric CRL, [13] considers 2 nodes, and [7] considers 8 nodes). Therefore, our experiments with up to 10 nodes are on par with the state-of-the-art interventional CRL.\n\nS. Buchholz, G. Rajendran, E. Rosenfeld, B. Aragam, B. Schölkopf, and P. Ravikumar. Learning\nlinear causal representations from interventions under general nonlinear mixing. NeurIPS 2023.", "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": "", "extra_scores": {}}, {"review_id": "4LiBHvmpEI", "reviewer": "Reviewer_fPsb", "summary": "Interventional causal representation learning aims to recover the causal graph for latent variables and simultaneously recover the latent variables. While identifiability has been established for the infinite sample regime, this is not practical. This paper aims to provide PAC-style bounds on identifiability (of both the graph and latent variables) in the finite-sample regime, assuming stochastic soft interventions and linear transformations from the latent to the observation space. Three prototypical algorithms (causal order estimation, graph estimation, and inverse transformation estimation) are proposed to estimate the graph and the latent variables, which pave the foundation, from which  PAC-style bounds have been established. Numerical assessments are conducted to provide complementary insights into the sample complexity results.", "questions": "I wonder if causal order estimation is necessary. Since the latent variables have yet to be estimated, their values and semantics are flexible. This implies that any given causal order could be acceptable, as these variables can be learned to fit the specified orders. Some edges would be pruned later, which can be done in the graph estimation stage.\n\nAdditionally, I wonder if there are other quantities beyond score differences and the correlation of score differences that could be used to recover the graph and the latent variables.\n\nFurthermore, it would be beneficial if the analysis could assess which variables and which parts of the graph are more prone to error, and to what degree, providing feedback on the estimated/recovered variables and graphs.", "limitations": "n.a.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Identifiability analysis is often conducted in the infinite sample regime, limiting its practical applicability. This paper extends identifiability analysis to the finite sample regime, representing a significant step forward.", "weaknesses": "The bounds are rather loose, which limits its practical applicability. Apart from that, these bounds do not provide sufficient guidance on designing better algorithms recovering latent variables and graphs. Having said so, I still welcome this type of theoretical papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind review and thoughtful questions. We address the raised questions as follows.\n\n**Causal order estimation.** The reviewer is correct in that since the causal graph and variables are latent, we can choose any ordering of the nodes and latent variables first and then assign meanings later. In fact, in Line 98, without loss of generality, we say that $(1,\\dots,n)$ is a causal order. However, after fixing this assignment, *we do not know* which node intervened in which environment (e.g., we do not know the causal order between the nodes intervened in $\\mathcal{E}^i$ and $\\mathcal{E}^j$). Hence, in our algorithms, we specifically identify each interventional environment with the corresponding intervened latent variable. For example, in Algorithm 3, we use the $m$-th interventional environment where node $k$ is intervened to recover the intervened variable $Z_k$ (up to some mixing) and assign it specifically to the $m$-th component of our latent variables estimate $\\hat{Z}$. \n\n **Approaches to CRL and score-based framework.** \n- There exist different approaches to interventional CRL that don’t use score differences. One such example is [9], in which the authors present a sparsity-promoting VAE-based approach.\n\n- Our motivation for investigating the score difference-based approach stems from the fact that it provides the strongest existing results for multiple settings. For the most general setting of nonparametric transforms and causal models, the only known provably correct algorithm is score-based [7]. For linear transformations, [4] provides the most general results (without restricting the causal models).\n\n- On an interesting note, the approach of [6] for Gaussian latent models and linear transformations is based on precision matrix differences, which exactly correspond to score function differences between Gaussian distributions.\n\n**Point-error analysis.** In our algorithms, we use thresholded decisions to obtain our graph estimate. Therefore, as a detection problem, the decisions that are most likely to fail are those with values that, in the noise-free setting, are closest to the decision boundary, i.e., the thresholds. In our algorithms, it is possible to keep track of the estimated values of these statistics as surrogates of the noise-free values and therefore assess how error-prone each decision is. That being said, the analysis in our paper is sequential, and errors can propagate. We consider the sample complexity analysis of approximate latent graph recovery, up to $k$-point errors, a critical future direction.", "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": "", "extra_scores": {}}]

Author rebuttal:
In the attached PDF, we provide a figure to update Figure 1b of the submitted paper with the updated experiment results. Specifically, there are two changes:
1) Each data point in old Figure 1b corresponds to a specific tuple $(N,n,d)$ (listed in Appendix G). For each $(N,n)$, the old plot has two points of $d$: $d=n$ and $d=15$. In the new figure, we present the two cases of $d$ in two figures for a clear presentation. The new plots show a monotonic behavior without major spikes.
2) In the new plots, we also added a data point for a larger number of samples to show that a good graph recovery rate is possible for latent dimension $n=10$.

Meta-review: The paper provides the first finite sample complexity results for causal representation learning, albeit under some technical conditions.

All reviewers were supportive of accepting the paper.

For a camera-ready version, please take into the account the comments from all reviewers regarding clarifications, for instance: notation/typos, discussion on the assumptions, experiment details and discussion about causal order estimation.
Decision: Accept (poster)