Sample Complexity of Interventional Causal Representation Learning

We thank the reviewer for the kind review and thoughtful questions. We address the raised questions as follows.

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}$.

Approaches to CRL and score-based framework.

• 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.

• 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).

• 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.

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.

We thank the reviewer for the kind review and thoughtful questions.

• ${\bf P}_I$ is the permutation matrix for permutation $I$, the intervention order. We will include the definition in the notations paragraph.

• 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”.

• 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}$.

[HTW] T.Hastie, R.Tibshirani, and M.Wainwright. Statistical learning with sparsity. Monographs on statistics and applied probability, 143, 2015.

• 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.

S. Buchholz, G. Rajendran, E. Rosenfeld, B. Aragam, B. Schölkopf, and P. Ravikumar. Learning linear causal representations from interventions under general nonlinear mixing. NeurIPS 2023.

We thank the reviewer for a thorough review and thoughtful questions. We hope our answers address the main concerns of the reviewer.

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.

• 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.

• 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$.

• 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$.

[HTW] T.Hastie, R.Tibshirani, and M.Wainwright. Statistical learning with sparsity. Monographs on statistics and applied probability, 143, 2015.

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.

We 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.

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.

In 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$.

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.

Theorem (Infinite samples – Graph). In 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}$.

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”.

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.

We thank the reviewer for finding our results interesting and the thoughtful questions. We address the questions as follows.

• Source of error in experiments. To 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.

• 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 via 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.