Consistency of Neural Causal Partial Identification
Authors: Jiyuan Tan
Jose Blanchet
Vasilis Syrgkanis
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal inference
Generative models
Partial identification
Primary area: causal_inference

Abstract: Recent progress in Neural Causal Models (NCMs) showcased how identification and partial identification of causal effects can be automatically carried out via training of neural generative models that respect the constraints encoded in a given causal graph [Xia et al. 2022, Balazadeh et al. 2022]. However, formal consistency of these methods has only been proven for the case of discrete variables or only for linear causal models. In this work, we prove the consistency of partial identification via NCMs in a general setting with both continuous and categorical variables. Further, our results highlight the impact of the design of the underlying neural network architecture in terms of depth and connectivity as well as the importance of applying Lipschitz regularization in the training phase. In particular, we provide a counterexample showing that without Lipschitz regularization this method may not be asymptotically consistent. Our results are enabled by new results on the approximability of Structural Causal Models (SCMs) via neural generative models, together with an analysis of the sample complexity of the resulting architectures and how that translates into an error in the constrained optimization problem that defines the partial identification bounds.

Consistency of Neural Causal Partial Identification
Jiyuan Tan
Jose Blanchet
Management Science and Engineering Stanford University Stanford, CA 94305 biyaantan@ttanfor..cco
Management Science and Engineering Stanford University Stanford, CA 94305
Vasilis Syrgkanis
Management Science and Engineering
Stanford University Stanford, CA 94305
veyrgk@stanford.co edu
Abstract
Recent progress in Neural Causal Models (NCMs) showcased how identification and partial identification of causal effects can be automatically carried out via training of neural generative models that respect the constraints encoded in given causal graph [52 3. However, formal consistency of these methods has only been proven for the case of discrete variables or only for linear causal models. In this partial identification setting with both continuous and categorical variables. Further, our results highlight the impact of the design of the underlying neural network architecture in terms depth and connectivity as well as the importance of applying Lipschitz regulariza- tion in the training phase. In particular, we provide a counterexample showing that without Lipschitz regularization this method may not be asymptotically consistent. Our results are enabled by new results on the approximability of Structural Causal Models (SCMs) via neural generative models, together with analysis of the sample complexity of the resulting architectures and how that translates into an error in the constrained optimization problem that defines the partial identification bounds.
work, we prove the consistency
NCMs general
Introduction
Identifying causal quantities from observational data is an important problem in causal inference which has wide applications in economics [1], social science [20), health care [34] [8], and rec- ommendation systems [9] One common approach to transform causal quantities into statistical
quantities using the ID algorithm [49] and deploy general purpose methods to estimate the statistical quantity. However,
the presence of unobserved confounding, typically the causal quantity of interest will not be point-identified by observational data, unless special mechanisms are present in the data generating process (e.g. instruments, unconfounded mediators, proxy controls). In the presence of unobserved confounding, the ID) algorithm will typically fail to return a statistical quantity and declare the causal quantity as non-identifiable.
One remedy to this problem, which we focus on in this paper, is partial identification, which aims give informative bounds for causal quantities based on the available data. At high level, partial identification bounds can be defined as follows: find the maximum and the minimum value that target causal quantity can take, among all Structural Causal Models (SCMs) that give rise the same observed data distribution and respect the given causal graph (as well as any other structural
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

constraints that one is willing to impose). Note that in the presence of unobserved confounding, there will typically exist many structural mechanisms that could give rise to the same observational distribution but have vastly different counterfactual distributions. Hence, partial identification can be formulated as solving a max and a min optimization problem 3
max \ min ((M), MEC
MEC
subject to PVV()- = P.M (V):
and
9M = DM=GM-.
where ((M) is the causal quantity of interest, .M" is the true model, V is the set of observed nodes, (V( is the distribution of V in SCM MM, C is collection of causal models and Gm is the causal graph of . (see Section [2 for formal definitions). Two recent lines of work explore the optimization approach to partial identification. The first line deals with discrete Structure Causal Models (SCMs), where all observed variables are finitely supported. In this case, []] becomes a I Linear Programming (LP) or polynomial programming problem and tight bounds can be obtained
37 27 explores ways of solving in continuous settings using various techniques [24 32 29 38 41].
40, 8 54, 56 14. The second line of work focuses on continuous models and
Recently, Xia et al. [T formalized the connection between SCMs and generative models (see also [33 for an earlier version of a special case of this connection). This work showcased that SCMs can be interpreted as neural generative models, namely Neural Causal Models (NCMs), that follow particular architecture that respects the constraints encoded in given causal graph. Hence, counterfactual quantities of SCMs can be learned by optimizing over the parameters of the underlying generative models. However, there could be multiple models that lead to the same observed data distribution, albeit have different counterfactual distributions. Xia et al. [51] first analyze the approximation power of NCMs for discrete SCMs and employ the max/min approach to verify the identifiability of causal quantities, without the need to employ the ID algorithm. Balazadeh et al. [ and Hui et al. (30), extend the method in [5]] and re-purpose it to perform partial identification by solving the min and max problem in the partial identification formulation over neural causal models.
However, for SCMs with general random variables and functional relationships, the approximation error and consistency of this optimization-base approach to partial identification via NCMs has not been established. In particular, two problems remain open. First, given an arbitrary SCM, not yet known if we can find an NCM that produces approximately the same intervention distribution as the original one. Although Xia et al. [51] show it is possible to represent any discrete SCM by an NCM, their construction highly relies on the discrete assumption and cannot be directly generalized to the general case. Moreover, Xia et al. (5l] use step functions as the activation function in their construction, which may create difficulties in the training process since step functions are discontinuous with zero gradient almost everywhere.
Second, since we only have access to n samples from the true distribution, PM((V) we need to replace the constraints in ① with their empirical version that uses the empirical distribution of samples P.M" (V) in place of the population distribution and looks for NCMs, whose implied distribution lies within small distance from the empirical distribution. Moreover, even the NCM distribution is typically only accessible through sampling, hence we will need to generate m. samples from the NCM and use the empirical distribution of the mn samples from the NCM in place of the true distribution implied by the NCM. Thus, in practice, we will use a constraint of the form m. (V)) & Onn where d is some notion of distribution distance and on accounts for
d(P.M (V), PMM(( the sampling error. It is not clear that this approach is consistent, converges to the correct partial identification bounds, when the sample size n grows to infinity. Balazadeh et al. [3] only show the consistency of this approach for linear SCMs. Consistency results concerning more general SCMs is still lacking in the neural causal literature.
In this paper, establish representation and consistency results for general SCMs. Our contributions are summarized as follows.
We show that under suitable regularity assumptions, given any Lipschitz SCM, we can approximate it using an NCM such that the Wasserstein distance between any interventional distribution of the NCM and the original SCM is small. Each random variable of the SCM is allowed to be continuous or categorical. We specify two architectures of the Neural Networks (NNs) that can be trained using common gradient- optimization algorithms (Theorem 2 Theorem 3 and Corollary

---

To construct the NCM approximation, we develop novel representation theorem of proba- bility measures (Proposition[] that may be of independent interest. Proposition iimples that under certain assumptions, probability distributions supported on the unit cube can be simulated by pushing forward a multivariate uniform distribution.
We discover the importance of Lipschitz regularization by constructing a counterexample where the neural causal approach is not consistent without regularization (Proposition 2
Using Lipschitz regularization, we prove the consistency of the neural causal approach (Theorem 4)
Related Work
There exists rich literature on partial identification of average treatment effects
(ATE) [37 4 27
44 45, 40 8 55] 56 14 7 39 26]. Balke and Pearl [ first give an algorithm calculate bounds on the ATE the Instrumental Variable (IV) setting. They show that regardless of
the exact distribution of the latent variables, it is sufficient to consider discrete latent variables as long
as all endogenous variables are finitely supported. Moreover, they discover that (I) an LP problem with a closed- form solution. This LP-based technique was generalized to several special classes of
SCMs 44 8 27 46 For general discrete SCMs, [4 36 53 consider transforming the problem ( into a polynomial programming problem. Xia et al. [5 discover the connection between generative
models and SCMs. They show that NCMs are expressive enough to approximate discrete SCMs. By setting C in problem ① to be the collection of NCMs, they apply NCMs for identification and
estimation.
For causal models with continuous random variables, the constraints in (T become integral equations, which makes the problem more difficult. One approach is to discretize the constraints. [24] uses stochastic process representation of the causal model in the continuous IV setting and transforms the problem into a semi-infinite program. [32) relaxes the constraints to finite moment equations and solves the problem by the Augmented Lagrangian Method (ALM). The other approach is to use generative models to approximate the observational distribution and use some metric to measure the distance between distributions.
33 first propose to use GAN to generate images. Later, [29] uses Wasserstein distance in the constraint and transforms the optimization problem into a min and max problem. Similarly, (3) solves the optimization problem using Sinkhorn distance to avoid instability during training. They propose to estimate the Average Treatment Derivative (ATD) and use ATD to obtain bound on the ATE, They also prove the consistency of the proposed estimator for linear SCMs. 41 uses a linear combination of basis functions to approximate response functions. (26) uses sieve to solve the resulting optimization problem in the IV setting. [99 proposes neural network framework for sensitivity analysis sis under unobserved confounding.
Organization of this paper In Section we introduce the notations and some basic concepts used throughout the paper. Next, in Section we demonstrate how to construct an NCM so that they can approximate a given SCM arbitrarily well. Two kinds of architecture are given along with an approximation error analysis. In Section 4 we highlight the importance of Lipschitz regularization by giving a counterexample that is not consistent. Then, leveraging the previous approximation results, we are able to prove the consistency of this approach under regularization. Finally, we compare our method with the traditional polynomial programming method empirically in Section 4.1
2 Preliminary
First, we introduce the definition of an SCM. Throughout the paper, we use bold symbols to represent sets of random variables.
Definition 1. (Structural Causal Model) A Structural Causal Model (SCM) is a tuple M = (V, U. F, P(U), Go). where V {V.)%y, is the set of observed variables; U {U, ) is the set of latent variables; P(U) is the distribution of latent variables; Go is an acyclic directed graph whose nodes are V. The values of each observed variable V; are generated by
V, fi (Pa(V.), Uv.), where V; & Pa(V:) and Uv. CU.
(2)
where F= ), Pa(V) is the set of parents of V in graph Go and Uv, is the set of latent variables that affect V. V₂ takes either continuous values R&d, or categorical in [ns]. We extend graph Go by adding bi-directed arrows between any V., V, E Go if there exists a correlated latent variable pair (Uv, Ut), Un E Uv, Ui E U Uv, We call the extended graph GM the causal graph of M.
3

---

When we write Pa(V)), we refer to the parents of V; in the Gy. To connect with the literature, the causal graph we define kind of Acyclic Directed Mixed Graph (ADMG), which is often used to represent SCMs with unobserved variables [49] Note that we allow one latent variable to enter several nodes, which differs from the common definition. We use ny and ny to denote the number of latent variables and observable variables. Let T C V be set of treatment variables. The goal is to estimate causal quantities under a given intervention T t. Formally, the structural equations of the intervened model are
T = t, E., Vi(1) fs (Pa(V.), &
We denote (t(t) to be the value of Vi under the intervention T = and (V)(V(t) to be the distribution of V ((t) in .M. The notion of a C² component (51] is defined as follows.
Definition 2 Comppnnet) For a causal graph G, subset C' c V is -oocoponeent if each pair V1, Vj E C' connected by a bi-directed arrow in G and C is maximal.
We provide concrete example in Appendix A to explain all these notions. We will make the following standard assumption about the independence of latent variables. Note that since we allow latent variables to enter in multiple structural equations, this is more a notational convention and not an actual assumption. Also note that under this convention a bi-directed arrow essentially represents the existence of a common latent parental variable.
Assumption 1. All the latent variables in U are independent.
To deal with categorical variables, we assume that latent variables that influence categorical variables contain two parts: the shared confounding that influences the propensity functions and the independent noise that generates categorical distributions.
Assumption 2. The set of latent variables consists of two parts U = (UI.... Une } U {Gv; V, is cutegorical). Precisely, Vf E V is categorical variable, the data generation pro- cess of V2 satisfies V; = arg maxkE|m.] { V/ + log (Je (Pa(V.), Uv))) Categoricall [9
where Gv, ....... .%,) are i.i.d. standard Gumbel variables, Uv. (U :-
This convention is without loss of generality at this point, but will be useful when introducing Lispchitz restrictions on the structural equation functions. The Gumbel variables in the assumption can be replaced by any random variables that can generate categorical variables. It can be proven that all discrete SCMs satisfy this assumption. Note that we implicitly assume that all categorical variables V; are supported on [n:] for some n,, It is straightforward to generalize all results to any finite support. Next, we introduce Neural Causal Models (NCMs). Definition 3. (Neural Causal Model) A Neural Causal Model (NCM) is a special kind of SCM where U = (UI....,U Unn } U {Gv, : Vi categorical), , all Ug are i.i.d. multivariate uniform variables, Gv, are i.i.d Gumblel variables and functions in (2) are Neural Networks (NNs).
The definition of NCMs we use is slightly different from that in [52) because we need to deal with mixed variables in our models. In ( we usually take C to be the of all SCMs. However, is difficult to search over all SCMs since (T) becomes an infinite-dimeniion dimensional polynomial programming problem. As an alternative, we can search over all NCMs. One quantity of common interest in causal inference is the Average Treatment Effect (ATE).
Definition 4. (Average Treatment Effect). For SCM M, the ATE at T = t with respect to T = to is given by ATEM(() EUNPPU) (L ((to)).
Partial identification can be formulated as estimating the solution to the optimization problems 3. The max and min values F and F define the interval [F, F which is the smallest interval we can derive from the observed data without additional assumptions. In particular, if = F, then the causal quantity is point-identifled.
Notations. We use ||- |1. || Ilx for the 1-norm and co-norm and [n]] for (1..... .n. Bold letters represent sets of random variables. We let Fr,, K2) be the class of Lipschitz. I-continuous functions f K1 -> K2. We may omit the domain and use Fr, when the domain clear from context. Let H(K,, K2) be the set of homeomorphisms from K₁ to K2. i.c. injective and continuous

---

maps in both directions. We define F2) = supfeer iee, ll.a - fill for function classes F2. We use standard asymptotic notation (()). Given measure 1 Rd and measurable function f: Rdi Rd the push-forward measure f# is defined [ μ (B) for all measurable sets B. We use P(X) to represent the distribution of random variable X. Let A. = {(P1. Pv)) Σx= P3 1, P; 2 0} be the probability simplex. We use Categorical(p), E A. to represent categorical distribution with event probability p. We let -(:-) be the Wasserstein-1 distance and Sx (1,, 2) be the Sinkhorn distance
12
with regularization parameter À > 0.
3 Approximation Error of Neural Causal Models
In this section, we study the expressive power of NCMs, which serves as a key ingredient in proving the consistency result. In particular, given an SCM M we want to construct an NCM M such that the two causal models produce similar interventional results. Unlike in the discrete case 51, latent distributions can be extremely complicated general cases. The main challenge how to design the structure of NCMs to ensure strong approximation power.
In the following, we first derive an upper bound on the Wasserstein distance between two causal models sharing the same causal graph. Using this result, we decompose the approximation error into two parts: the error caused by approximating structural functions via neural networks and the error of approximating the latent distributions. Then, we design different architectures for these two parts.
Decomposing the Approximation Error First, we present a canonical representation of an SCM, which essentially states that we only need to consider the case where each latent variable U; corre- sponds to a C2 component of G.
Definition (Canonical representation), SCM M with causal graph G has canonical form if
1. The set of latent variables consists of two sets,
U = =UCC C' is C2 -commpnnntt g} U (cv, = ... (y.) V₃ is categorical
where Uc and oy¹ are independent and 93 V: are standard Gumbel variables.
2. The structure equations have the form
fo (Pa(Vi)) Uv.). { 9 log (fi (Pa(Vi), Uv.le
Vi is continuous,
V.
arg max
Vi is categorical, 1l, 1,
(3)
where Uv {Uo V C,C is a Co-component of 9} and (x)x is the k-th coordinate of the vector x. We further assume that fi are normalized for categorical variables.
Given a function class F, the SCM class M(g, U) consists of all canonical SCM models with causal graph G such that fo E F, i E [ny].
Proposition 4 in the appendix shows that any SCM satisfying Assumption 12 can be represented in this way and provide example in Appendix B.I to illustrate how to obtain the canonical representation for a given SCM. Therefore, we restrict our attention to the class MGG F,F,F, U). For two SCM classes M(G F, M(G, F. Ú), we want to study how well we can represent the models in the first class by the second class. The Wasserstein distance between the intervention distributions is used to measure the quality of the approximation. To approximate the functions in the structural equations, we need to make the following regularity assumptions on the functions.
Assumption 3. If V2 is continuous, fa in (3) are Lipiscchitzz continuous. If V; is categorical, the propensity functionss (PP((V)) Vv;) - PVV j\Pa(VV), Uv:). E [m.] are -ipsciit continuous. There exists constant K > 0 such that maxie (llV, [U,] & K.
The following theorem summarizes our approximation error decomposition.
Theorem Given any SCM model M E MiG, U), let the treatment variable set be T (Th 1 and suppose that Assumption and 3 hold for M with Lipschitz constant L, constant K.
5

---

Depti
Madd: Ri Depa
Now antente
Space-lilleg
Lipcciis lemommopienn
Gumbie Solmmss
P(U)
Unik0.1)
(a) Architecture of wide neural network (b) This figure demonstrates the first two parts our architecture. Each interval in the yellow box corre- sponds to one coordinate of input in the left figure. We first push forward uniform distributions to different cubes. Then, using Assumption f we adapt the shape of the support and push the measure from unit cubes to the original support of P(U). In this way, we can approximate complicated measures by pushing forward uniform variables.
4- dimmonssional output. The first (yellow) part approximates the distribution components of the support using the results from [43] The width and depth each block in this part are W1 and L1- The second (blue) part transforms the distributions on the unit cube to the distributions on the support. The width and depth of cach block in the blue part W2 and Lg- The third (green) part is the Gumbel-Softmax layer. combines the distributions on different connected components of the support together and outputs the final distribution.
different connected
For any intervention =t and M M(G.F,Ü), we have
ny
Ilff filoo + W (PM(U), pm pu(ti)) (4)
w (PM PM) (VM()
C)
Σ
where C)(L,K) is constant that only depends on L, K and the causal graph G and Sis Si are structural functions of M and M respectively.
Theorem I separates the approximation error into two parts, which motivates us construct the NCM in the following way. First, we approximate the functions f. (3) by NNs f.. Then, we approximate the distribution of latent variables by pushing forward uniform and Gumbel variables using neural networks, i.e., Üc,- = أزق (c,,) where {C}} are C2 components and Zc, are multi-variate uniform and Gumbel random variables. The structural equations of the resulting approximated model M are
(Pa(V.), (0s (Zc, )ue, EU arg max {9k- - log (f: (0) (o1e evv.
V is continuous,
(5)
Vi is categorical,
wheres Noj are constants to be specified later.
For the first part, need approximate Lipsehitz continuous functions. For simplicity, assume that the domain of the functions are uniform cubes. Similar arguments hold for any bounded cubes. We denote NWA,,k (W, L) be the set of ReLu NNs with input dimension k1, output dimension
k2, width W and depth L. has been shown that eNNN ky. (2d, 10, Lo) Fr. 1j ,R) <
O(L 2/k1 53). where e(-; :) denotes the approximation error defined in Section 2 For vector valued function, we can use wider NN to approximate each coordinate and get a similar rate.
For the second part, we approximate each U; individually by pushing forward i.i.d. multivariate uniform and Gumbel variables Uc (Zc.) since the latent variables are independent by Assump- tion I To do so, we examine under what assumptions on the measure over IR we can find NN such that W (ā P) is small, where X(-) is some reference measure.
3.1 Approximating Mixed Distributions by Wide Neural Networks
In this subsection, we will extend the results in 43 to construct wide neural network as the push-for push-forward forward map. turns out that to get a good approximation of the targeted distribution, the shape of the support is essential.

---

Assumption 4 (Mixed Distribution). The support of measure P has finite connected components C1 C2.C2. C.....CC -NNo i.e., supp(L) U Cs, and each component C, satisfies H(OO 11 C,) n Fr. 1 ( & 0 for some of 7 O. Recall that ; is the set of homeomorphisms from K1 to K2 defined at the end of Section
Assumption Cnnompasses almost all natural distributions. For example, distributions supported on [0, 1 and closed balls. finitely supported distributions and mixtures of them all satisfy this assumption. Assumption 4 allows us to transform the support of the targeted distribution into unit cubes and the nice geometric properties of unit cubes facilitate our construction.
Now, briefly explain the construction of the push-forward maps. An example is provided in Appendix to illustrate the construction. The NN architecture consists of three parts (see Figure Ia). The input dimension is the same as the number of connected components of the support Ne. For
each component C,, let H; E H( 1]de C.) n FL 1 C.), where df is the dimension of component C; in Assumption 4 By P (Hi)) # (H, "P on C, we can approximate (H1 P first, which is supported on unit cube. 43 constructs wide NN I of width W and constant depth such that W (0 (Hz) ب IP) & OWW-1/d)) where À is the uniform measure on [0, 1]. Then, we approximate the Lipschitz map H. C2 to pull the distribution back to C. These are the first two parts (yellow and blue blocks in Figure Tab of the architecture.
Suppose that the output of i-th coordinate in the first two parts is T. the Gumbel-softmax layer in the third part (green box) combines different components of the support. In particular, we want to output th with probability ps IP.C.). Let V [+1 Ty this can be achieved by outputting VX,, where X (X1,'.. X XNe) ) is a one-hot random vector with P(X; 1) P:- To use backpropagation in training, we use the Gumbel-Softtax trick (31] to (approximately) simulate such a random vector, where > O is the temperature parameter (a hyperparameter) and
X7 D exp((log GG))/)
G ~ Gumbel(O, 1) are i.i.d. standard Gumbel variables. As T - 0, the distribution of X converges almost surely the categorical distribution (36] Proposition 1]. In partieular, when T = we denote X =arg max, (log G. The output of the last layer is VX Note that the Gumbel-softman function is differentiable with respect to parameter {log(p;) Ji=,,... ..e. Therefore, we can train the network with common gradient-base -ased algorithms. Putting things together, we obtain the following theorem.
Theorem 2. Given any probability measure I on Dd that satisfies Assumption 4 let X be the Lebesgue measure on [0, 1J8e,, where No is defined in Assumption 4
There exists a neural network
9 = 93 o 92 o タ1 with the above architectsure (Figure Tap such that
W 1) < <0 <OWW"V/ )
+ LLz
-2/ max, ( ((--TlogT))
((t),, Here, gi,i = 1,2 has the separable form ( (øt
"......,""" (INN)) and of ENN 1.49 O(1,
oe a dg), I2), E [Nc]. (dg) are the dimension of cubes in Assumption 93 is the Gumbel-Softmax layer with temperature parameter T O.
Note that 93 (the Gumbel-softmax layer) is actually random function since the coefficient vector X is a random variable. In this sense, _ can be viewed as pushing forward uniform and Gumbel variables using neural net.
3.2 Approximating Mixed Distributions by Deep Neural Networks
In this subsection, we will show that under one additional assumption on the distribution, deep ReLu networks have stronger approximation power in approximating distributions, which means we can use fewer computational units to achieve the same worst-case theoretical approximation error.
Assumption 5 (Lower Bound). Suppose that IP is supported on compact set K C CR,, there exists constant C > 0, f H( 1]d, K) n F2 1]d, ; K), such that for any measurable set B C [0, 1]d (f > C,>(B). Besides, if > 0, IT vanishes on the boundary a(0, 1]a
Assumption 5 implies that dd/d(f= PP) exists and is lowered bounded by a constant Cy. The next proposition extends the Skorohod representation theorem 48). It shows that under Assumption 5 it
7

---

is possible to simulate any distribution on the unit cubes with Hölder continuous curves and uniform
distribution on [0, 1].
Proposition 1. Let X be the Lebesgue measure [0, 1]. Given any probability measure P that
satisfies Assumption 5 there exists a continuous curve Ty [0,1] - supp(P) such that " P.
Furthermore, if d I. y is 1/d-Hölder continuous.
Results from 533 show that we can approximate any Hölder continuous d-dimensional function with
index a by a deep ReLu network with depth I. and error O(T,-a//d) Leveraging this result, we can replace the first part of the architecttre in the previous subsection with deep ReLu networks (See Figure 8 in the appendix). The remaining two parts are the same as the construction in Figure Ia The following theorem gives sharper bound on the approximation enror compared with Theorem 2
Theorem 3. Under the Assumption 4 if in addition, P constrained to each component satisfies Assumption 5 there exists a neural network 9 = 03 o 92 o 91 with the above architecture such that
W(0+h,P) & O 2/ max, (d.) L2 2/ max; (d9) Trr-loog))
where de are the dimensions of the connected components in Assumption 4 gi, i = 1, has the form
(11))...... ,0 (xNc)) and şी a L1). Ø2 93, are the same in Theorem 2
Let N be the number of nonzero weights in a neural network, Theorem 3 shows that a deep NN can achieve O(N-2/6 error while by Theorem error. Now, we can put things together to construct NCM approximations. For simplicity, we omit the input and output dimensions of the neural network. As we mention in previous sections, our construction (5) consists of two parts, f. approximating the structural functions f( in (3,, and (Z,) D5, 02.5 (1,j(Zz) approximating the latent variables Uy. Let NCMg Fi, F2, 7) be a collection of NCMs with structural equation (5) and
wide network can only achieve O(N
E Wi.....
No.)) 91.3 ", ) E F1,92. = (02..' ,92.3
No.) ),02 E F2,
where Nc.; is the number of connected components for U, and F; are function classes.
Corollary 1. Given a causal model M E MMG.FL. U), suppose that Assumptions hold and the distributions of Uc for all C -c-component satisfy the assumptions of Theorem 3 Let dmn and dout be the largest input and output dimension of fs in and d be the largest dimension of all latent variables. There exists neural causal model
M E NCMg(NN((I) (dmax d NNN (9
,NN (0 ((dmax))) L2) .))
with structure equations
(5) For any intervention T = t, M satisfies
w (PM (V(t)), PM) < O 2/d A + L -////
Lo 22/d
+ (5- T ()g.
Similar approximation results also hold for wide NN approximation, as presented in Section 3.1 The proof can be easily adapted to the wide NNs architecture.
4 Consistency of Neural Causal Partial Identification
In this section, we prove the consistency of the max/min optimization approach to partial identification. In the finite sample setting, we consider the following estimator F, of the optimal values of (T).
F.
arg min
Ea-py E (F()((()) ... Vay (f))).
(F Fi. Fannsaa)
s.t. Sx, (PM (V), P.M' (V)) < an.
where PMV ... are the empirical distribution P.M PM with sample size n, m, pe is some given measure and J.,, will be specified later. For example, the counterfactual outcome (E is special case of the objective. Our results can be easily generalized to any linear combination of objective functions of this form. We use the Sinkhorn distance because it can be computed efficiently in practice [15]. We want to study if F2 gives useful lower bound as n co.
8

---

To match the observational distribution, we need to increase the width or depth of the NNs we use. As the sample size increases, the number of parameters also increases infinity, which creates difficulty in the analysis. To obtain consistency, we need to regularize the functions while preserving their approximation power. Surprisingly, if we do not use any regularization, the following proposition implies that consistency may not hold even if the SCM is identifiable.
Proposition 2 (Informal, see Proposition 5 for formal version). There exists a constant e > O and an identifiabee SCM M satisfying Assumptions 7 such that for any >> 0, there exists an SCM M. satisfying W(P. (V), JM, (V)) S c and AATE - ATEM, >
Here,M' is the ground-trutt model and M, are the models we to approximate M Proposition 2 implies that we need some regularization on MM. Otherwise, even if the observation distributions are close, their ATES can be far away. In particular, we may want to regularize the Lipschitz constant of the NN. Much work has been done to impose Lipschitz regularization during the training process 50 22 42 [0]. We denote Lip(f) be the Lipschitz constant of function f and define the truncated Lipschitz NN class,
, d1.d2 (W, L) = {max{ min : E NN (W, Lip(f) & Lr}.
For simplicity, we omit the dimensions and use shorthand NN (W, L). The next theo- rem gives the consistency result of the min estimator. To state the theorem, we define F. E M. (t), ..... Vay (4)) to be the true value and FL to be the optimal value of the following optimization problem over SCMs with Lipschitz constant L..
FL
arg min U)
E E (F Vay (t))..
s.t.W(PsM(V) (V), pM (V))=0 =0,
where the minimum is taken over M (G. U) with FK = {f |flll & K, FL} and all latent distributions P(U). Note that if L is the Lipschitz bound Ly that we assume on our structural functions, then FL is the sharp lower bound.
Theorem Let M be any SCM satisfying the assumptions of Corollary 7 Suppose that the Lipschitz constant of functions in M is L.f. F TR.Vv - TR. in (6) is Lipschitz continuous and O, let K be the constant in Assumption L v
ddi / maax Lef.
Fo,n =NN (Wo.n θ (log dmax)) Fi.m = NN (d Li,,),
F2. -N (O((d))))) )), Lin))
where dy dmaao din dmnax and dout are defined in Corollary take the radius to be on = en + Sns En
OW 0.
+ + Iun
-2/1
+ Tn log Tn);
8n = =0mmm -1/(d +2)
log m. + 8n +
5n = O(n 12, log2 (n)).
di (2dg " ),)), 2,2 limm min Wo,,, (log(nm,)) )m)) -11-
m = -I(n), Lin = 0
0o. then with probability 1, [lim inf Fn, lim sup, Fn] C [[F',,
Note that our theorem shows that the lower limit of the solution is large than the point p4,, where L, is slightly larger than the original constraint 4, we impose on the structural functions. Hence, this point can potentially be slightly smaller than the sharp bound pd1, This worsening is due to the fact that we need to use NNs that satisfy a slightly worse Lipschitz property, to ensure that we have sufficient approximation power. Although Theorem 4 does not guarantee {F,} converges to point, it states that (Fr) may oscillate in the interval |= F.], which will still give useful lower bound to ground-truth value F.. In particular, the graph is identifiable, we have F = F and }F,} converges to F". Also, note that in Theorem 4 we use wide NNs rather than deep NN for Fu,n because results in [53] show that wide NNs can approximate Lipschitz functions while controlling their Lipschitz constants (a property that is not yet established for deep NNs). Similar results can be obtained if wide neural nets are used for all components, invoking Theorem 2
As special case, we leverage Theorem for non-asymptotic rate for the ATE without confounding.

---

Proposition 3 (Hölder continuity of ATE), Given two causal models M.M E ML.
satisfying Assumption 7 and Assumptiin 3 let their observational distributions be V, μ. Suppose the norms of all variables are bounded by K > O. (I) (Overlup) is absolutely continuous with respect to one probability measure P and the density Pu (1)Pu(T) = x) 3 5 > 0 for x almost surely and & E 12) and (2) (No Confounding) there is no confounding in the causal graph G, we have
J, (EM( - JM (())))()) & 2Cw W(n,)) + 2(L 1)th (v, (12 - -1),
where Cw 44L4 1) K + 2K max {(L + 1) Corollary Let FT in Theorem to be assumptions in Proposition Jand Theorem 4 hold, hhold, with probability at least 1 Onn=)) we have |Fn F.| < <((aa,, where Fns Fx, On are defined in Theorem
YY ~ Unif (1, t2]), 0. Suppose that the
4.1 Experiments
In this section, we examine the performance of our algorithm in two settings, We compare our algorithm with the Autobounds algorithm [14 in a binary IV example [14 and in continuous IV m Since Autobounds can only deal with discrete models, we discretize the continuous model for comparison purposes. The implementation details are provided in the Appendix [D] The setting of the first experiment is taken from [14] Section D.1J. This is binary IV problem and we can calculate the optimal bound using LP 4.. We find that our bound is close to the optimal bound. The second experiment is a general IV example where the treatment is binary but the rest of the variables are continuous. The program that Autobounds solves after discretization contains Re 2 variables. Even with such fine discretization, the bound obtained by Autobounds is not tighter than our NCM approach. The details of the structural equations and analysis can be found Appendix D We also provide an extra experiment on the counterexample of Proposition 5 in the appendix to show the effect of Lipschitz regularization.
Setting
Algorithm
Average Bound
Optimal Bound
True Value
NCM (Ours)
[-0.49.0.05]
[-0.45, -0.04]
Binary IV
-0.31
Autobounds
[-0.45,00005]
10.45.00.04
NCM (Ours)
[2.49,3.24]
General IV
Autobounds
[1.40, 3.48]
Table 1: Experiment results of 2 IV settings. The sample sizes are taken to be 5000 in each experiment.
STD is the standard derivation. The experiments repeated 10 times for binary IV and 50 times for continuous IV. In all experiments, the bounds given by both algorithms all cover the true values.
Conclusion In this paper, we provide theoretical justification for using NCMs for partial identifica- tion. We show that NCMs be used to represent SCMs with complex unknown latent distributions under mild assumptions and prove the asymptotic consistency of the max/min estimator for partial identification of causal effects in general settings with both discrete and continuous variables. Our results also provide guidelines on the practical implementation of this method and on what hyper- parameters are important, as well recommendations on values that these hyperparameters should take for the consistency of the method. These practical guidelines were validated with a small set of targeted experiments, which also showcase superior performance of the neural-causal approach as compared to prior main contender approach from econometrics and statistics, that involves discretization and polynomial programming.
An obvious next step in the theoretical foundation of neural-causal models is providing finite sample guarantees for this method, which requires substantial further theoretical developments in the under- standing of the geometry of the optimization program that defines the bounds on the causal effect of interest. We take first step in that direction for the special case, when there no unobserved confounders and view the general case as an exciting avenue for future work.
Acknowledgement Research Award.
Vasilis Syrgkanis is supported by NSF Award 113-2337916 and 2022 Amazon
'The code can be found in http:://hhhbb..oooiyyaaaaaaaaaaa
10

---

References
[1] Joshua Angrist and Guido Imbens. Identification and estimation of local average treatment effects, 1995.
[2] Martin Anthony, Peter L Bartlett, Peter Bartlett, al. Neural network learning: Theoretical foundations, volume 9. cambridge university press Cambridge, 1999.
[3] Vahid Balazadeh, Vasilis Syrgkanis, and Rahul G. Krishnan. Partial identification of treatment effects with implicit generative models, October 2022.
[4] Alexander Balke and Judea Pearl. Counterfactual probabilities: Computational methods, bounds and applications. In Uncertainty Proceedings 1994, pages 46-54. Elsevier, 1994.
[5] Alexander Balke and Judea Pearl. Bounds on treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 111439: September 1997.
[6] Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
[7] Alexis Bellot. Towards bounding causal effects under markov equivalence. arXiv preprint arXiv:2311.0725,, 2023.
[8]
Blai Bonet. Instrumentality tests revisited, January 2013.
[9] Léon Bottou, Jonas Peters, Joaquin Quiñonero- Candell,, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
[10] Leon Bungert, René Raab, Tim Roith, Leo Schwinn, and Daniel Tenbrinck. CLIP: Cheap Lipschitz Training of Neural Networks. In Abderrahim Elmoataz, Jalal Fadili, Yvain Quéau, Julien Rabin, and Loic Simon, editors, Scale Space and Variational Methods in Computer Vision, volume 12679, pages 307-319, Cham, 2021. Springer International Publishing.
[11] Victor Chernozhukov, Han Hong. and Elie Tamer. Estimation and confidence regions for parameter sets in econometric models 1. Econometrica, 1243):1243-1284 2007.
[12] Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xaviis Xavier Vialard, and Gabriel Peyré. Faster wasserstein distance estimation with the sinkhorn divergence. Advances in Neural Information Processing Systems, 33:2257-2266 2020.
[13] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustmess to adversarial examples. In International conference on machine learning. pages 854 863. PMLR, 2017.
[14] Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, and Ilya Shpitser. An automated approach causal inference in discrete settings, September 2021.
[15] Jean Feydy. Geometric data analysis, beyond convolutions. Applied Mathematics, 2020.
[16] Jean Feydy, Thibault Séjouréé, François- Xavier Vialard, Shun-ichi Amari, Alain Trouve, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. The 22nd International Conference on Artificial Intelligence and Statistics, pages 2681-2690, 2019.
[17] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3-4):707-738, 2015.
[18] Dennis Frauen, Tobias Hatt, Valentyn Melnychuk, and Stefan Feuerriegel. Estimating average causal effects from patient trajectories. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 7586-7594, 2023.

---

[19] Dennis Frauen, Fergus Imrie, Alicia Curth, Valentyn Melnychuk, Stefan Feuerriegel, and Mihaela van der Schaar, A Neural Framework for Generalized Causal Sensitivity Analysis, April 2024.
[20] David A Freedman. Statistical models and causal inference: a dialogue with the social sciences. Cambridge University Press, 2010.
[21] Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression in met- ric spaces via approximate lipschitz extension. IEEE Transactions on Information Theory, 63(8):4838-4849 2017.
[22] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing Lipschitz continuity. Machine Learning, 110(2):393 416, February 2021.
[23] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, I 110:393-416, 2021.
[24] Florian Gunsilius. A aath-sampling method to partially identify causal effects in instrumental variable models, June 2020.
[25] Chris H. Hamilton and Andrew Rau-Chaplin. Compact hilbert indices for multi-dimennional data, In First International Conference on Complex, Intelligent and Software Intensive Systems (CISIS 07), pages 139- 146. IEEE.
[26] Sukjin Han and Shenshen Yang. A computational approach identification of treatment effects for policy evaluation. Journal of Econometrics, 240(1): 105680, 2024.
[27] James J. Heckman and Edward J. Vytlacil. Instrumental variables, selection models, and tight bounds on the average treatment effect. In Wolfgang Franz, Michael Lechner, and Friedhelm Pfeiffer, editors, Econometric Evaluation of Labour Market Policies, volume 13, pages 1-15. Physica- Physica-Verlag HD, Heidelberg, 2001.
[28] David Hilbert. Über die stetige abbildung einer linie auf ein flächenstück. Dritter Band: Analysis- Grundlagen der Mathematik- Physik Verschiedenes: Nebst Einer Lebensgeschichte. pages 1-2, 1935.
[29] Yaowei Hu, Yongkai Wu, Lu Zhang, and Xintao Wu. A generative adversarial framework for bounding confounded causal effects. Proceedings of the AAAI Conference on Artificial Intelligence, 12144-11210--221,,, May 2021.
[30] Yaowei Hu, Yongkai Wu, Lu Zhang, and Xintao Wu. A generative adversarial framework for bounding confounded causal effects. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 22104-12112 2021.
[31] Eric Jang, S. Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax. ArXiv, abs/166 hts/16111 1.01144, 2016.
[32] Niki Kilbertus. Matt J. Kusner, and Ricardo Silva. A class of algorithms for general instrumental variable models, October 2020.
[33] Murat Kocaoglu, Christopher Snyder, Alexandros G Dimakis, and Sriram Vishwanath. Causal- gan: Learning causal implicit generative models with adversarial training. arXiv preprint XX0x:1709.02023 2017.
[34] Mohammad Lotfollahi, Anna Klimovskaia Susmelj, Carlo De Donno, Yuge Ji, Ignacio L Ibarra, F Alexander Wolf, Nafissa Yakubova, Fabian J Theis, and David Lopez-Paz. Compositional perturbation autoencoder for single-cell response modeling. BioRxiv, 2021.
[35] Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance, May 2018
[36] Chris J. Maddison, Andriy Mnih, and Yee whye Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables, March 2017.
12

---

[37] Charles F Manski. Nonparametric bounds on treatment effects. The American Economic Review, 80(2):319-322 1990.
[38] Chengzhi Mao, Augustine Cha, Amogh Gupta, Hao Wang, Junfeng Yang, and Carl Vondrick. Generative interventions for causal learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 3947-3956, 2021.
[39] Valentyn Melnychuk, Dennis Frauen, and Stefan Feuerriegel. Partial Counterfactual Identi- fication of Continuous Outcomes with Curvature Sensitivity Model. Advances in Neural Information Processing Systems, 36:32020-32000, December 2023.
[40] Caleb H. Miles, Phyllis Kanki, Seema Meloni, and Eric J. Tchetgen Tchetgen. On Partial Identification of the Pure Direct Effect, September 2015.
[41] Kirtan Padh, Jakob Zeitler, David Watson, Matt Kusner, Ricardo Silva, and Niki Kilbertus. Stochastic causal programming for bounding treatment effects. In Conference on Causal Learning and Reasoning, pages 142-176. PMLR, 2023.
[42] Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgöwer. Training robust neural networks using Lipschitz bounds. IEEE Control Systems Letters, 6:121-126, 2021.
[43] Dmytro Perekrestenko, Léandre Eberhard, and Helmut Böleskei. High-Dimensional Distribution Generation Through Deep Neural Networks, August 2022.
[44] Roland R. Ramsahai. Causal bounds and observable constraints for non-deterministic models. Journal of Machine Learning Research, 13(29):829 848,,88888888 2012.
[45] Amy Richardson, Michael G. Hudgens, Peter B. Gilbert, and Jason Fine. Nonparametric Bounds and Sensitivity Analysis of Treatment Effects. Statistical Science, 29(4), November 2014.
[46] Michael C. Sachs, Gustav Jonzon, Arvid Sjölander. and Erin E. Gabricl. A general method for deriving tight symbolic bounds causal effects, December 2021.
[47] E. Shchepin. On hölder maps of cubes. Mathematical Notes, 87:757-767, 2010.
[48] Anatoly V Skorokhod. Limit theorems for stochastic processes. Theory of Probability & Its Applications, (3))2611220,) 1956.
[49] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables. December 2002.
[50] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[51] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neural connection: Expressiveness, learnability, and inference, October 2022.
[52] Kevin Xia, Yushu Pan, and Elias Bareinboim. Neural causal models for counterfactual identifi- cation and estimation. arXiv preprint arXiv:2210.00035, 2022.
[53] D. Yarotsky. Optimal approximation of continuous functions by very deep relu networks. ArXiv, hass/800.003620 2018.
[54] Junzhe Zhang and Elias Bareinboim. Bounding causal effects continuous outcome. Proceed- ings of the AAAI Conference on Artificial Intelligence, 35(13): 12207-12155 May 2021.
[55] Junzhe Zhang and Elias Bareinboim. par-meraee methods for partial identification causal effects. Columbia CausalAI Laboratory Technical Report, 2021.
[56] Junzhe Zhang, Jin Tian, and Elias Bareinboim. Partial counterfactual identification from observational and experimental data, October 2021.
13

---

A
V/ f2(U1, U2), Illustration of Notions in Section 2
V2
U2
Un
V/2
Vi
V3
V4
V/
V2
V3
U1
Figure 2: An SCM example.
Figure 3: The causal graph of this SCM.
To further explain the notions in Section with the following structure equations.
consider the following example. Let M be SCM
Vi fi(V, U1),
V/3 = fa(V,, V2, U2, U4),
(8)
V1
Ua),
V/3 - SV(V,, U2),
where U1 and U, are correlated and U3. U2 and (U1, U2 are independent. The causal model is
shown in Figure 2 its causal graph is shown in Figure 3 In this example, Uv, {U1}. [.1..0. U v.
(U1, U2]. Vi3 {Ug, U2). Uv, {U3, 11), Uv, {Uz)- Since U1. U2 are correlated. C1
(V1, 1/2, 1/3} is one C² component because all nodes in C₁ are connected by bi-directed edges. Note
that (Vi, V2, Vs, V4 ] not C2 component because and V/2 not connected by any bi-directive edge. The rest of C components are C2 (V4. V/J, C3- (Vg, V4).
Now, we consider the intervention Vi f. Under this intervention, the structure equations can be obtained by setting V1 = f while keeping all other equations unchanged, i.e.,
(t( =
V2(t) =f((U1,U2)
V/3 = fa(V,, V2, U2, Un),
Va = E2(V,UU,, U4),
(t(() = fo Uz).
The figure of this model under intervention is shown in Figure
V2(U)
U2
U3
V1(E
(t
Va(t)
Vs(t)
Ui
U4
Figure 4: The SCM after intervention V1 t.
14

---

B Proof of approximation Theorems
B.1 Illustration of how to construct canonical representations and neural architectures
In this section, illustrate how construct canonical representations and neural architectures given a causal graph via simple example. We consider the example in the previous section. The causal graph shown in Figure 3
V/2
V3
Vi
V3
V₂
V
F-2
Fi
Z2
Figure
The canonical representation of Fig-
Figure 6: The neural network architecture.
ure
3
one latent variable for each C² component. As explain Appendix A this causal model has three C2 components, (V1, V2, V3J, { (V3, V1), (V,, V- In the canonical representation, exactly the latent variables enter their corresponding C2 component. The structure equation this SCM is as follows.
Following the construction in Proposition 4
V1 fi(V,, E1),
1/2 f2(Ei),
V/3 fa(V1, V2, E1, E2),
(9)
V1 (1(33-E2),
V/3 So(V4, Ea),
If we set E U2 F3 Uz. 10 is equivalent to (8) Therefore, we can see from this example that the canonical representation does not lose any information about the SCM.
Now, we show how to construct the NCM architecture from a canonical representation. As we mentioned Section 3, approximate the latent distribution by pushing forward uniform and Gumbel variables. The structure equation of the NCM is
V f (V2, 21 (Zz)),
1/2 1 (Z))),,
V/ f (V1, V2, 01 (Z1), (Z2)),
(10)
V. 18" (V3-9²" 81 (Z2)),
V, 1 (V4, 8: (Za)),
where J 8: are neural networks, Z, are join distribution of independent uniform and Gumbel variables, and 2 has the special architecture described in Section 3.1 and Section 3.2. Figure shows the architecture the NCM. Each in-edge represents an input a neural net.
B.2 Proof of Theorem
The causal graph & does not specify how latent variables influence the observed variables. There could be many ways of recovering the latent variables from graph G. 7shows an example where two different causal models have the same causal graph. The next proposition gives canonical representation of causal model.
15

---

U1
U22
U3
V12
V2
V/3
Vi
V2
V3
U1
Figure 7: Example: two different SCMs with the same causal graph.
Proposition 4. Suppose that Assumption Mand Assumption 2 hold, given any SCM M with causal graph 9 and latent variables U, can construct canonical SCM M of the form 3 by merging the latent variables in U such that M and M produce the same intervention results. Besides, functions in M have the same smoothness M.
Proof of Proposition 4 Let = {Gv, : Vi is categorical) and the latent variables in the original model M be U (U ... and the structure equations of M have the form
.Ung } G. By Assumption and Assumption 2 U are independent
Jt (Pa(V.), Uv:),
Vi is continuous,
V
arg maxxe(n.)
9k + log (Je (Pa(V.), Uv, vv,))a )
V, is categorical,
where of are i.idd. standard Gumbel variables and Uv: {UI,..., Uno } contains the latent variables that affect V/, We regroup and merge the variables U; to make the model have canonical form while not changing the functions in the structure equations. Let DI, Dne C V be the C (2-component of M. For each U,, we define the vertices that are affected by U, as
T(U.) = (V, Us Uvz).
We partition {U1,--. -nng) into no sets ÚI.... ... U no in the following way. For each Uk. Uy is in the set Ü. if (UUx) C D;. If there are two components Di, Dj satisfy the condition, we put Un into either of the sets Ü., Ú J. Let Ú, have the same distribution as the joint distribution of the random variables in set Ü. Let M MEEM M,G,F. Ū)) the SCM with structure equations
f. (Pa(Vi), Un.,..., ......)))) arg maxke(ms)
Vi is continuous,
V
nU, nUv, & 0, i [nv].
( 9 + log (Is (Pa(V)), Ukm.. )
Vi is categorical,
Here, we slightly abuse the notation ft. fs ignores inputs from Uk. ....... ki, that are not in Uv. Note that UI,... Ú Unc. G has the same distribution as U because only merge some latent variables. In addition, the functions in the new model M has the same smoothness as the original model.
We first verify that the causal graph of M is G. If there is a bi-directed arrow between nodes V,, V, in G. by the independence assumption, there must be one latent variable Us E Uv, O NU,, There exist one D; such that (U*. C Dj and U, n Uy, + 0, Ü, n U Vv + 0. Therefore, Új will affect both V; and V, and there is bi-directed arrow between node V,, Vy in 9MM- Suppose that there is a bi-directed arrow between node V,, in G Gra, it means there exist Ug such that NuV * 0, 0.Ü + 0. Let UI E e..nUv UI ÜK I nUv, then
E E I(Ui)) c DR, E I(Ui)) C Dr.
Since D3 is C2 -c-oomonnet,, there exist bi-directed arrow between node Vi, V, in Therefore, = Gyn
16

---

Finally, we verify that M and M produce the same intervention results. The intervention distribution can be viewed as the push-forware of the latent distribution, i.e.. V FUU,, and the intervention operation only changes the function F. In our construction, we only merge the latent variables and leave the functions in structure equations being the same (except that they may ignore some coordinates in input). For any intervention T = f, suppose in M we have V = (T) Then, in M, get (t) = (U)) Since U and Ú has the same distribution, the distribution of (tt), (tt) are the same.
Proof of Theorem
! The structure equations of M have the form
fi (Pa((V)), Uv).
Vi is continuous,
V arg max { + (f: Uv)V))
Vi is categorical, [| 1,
where Vi are i.i.d. standard Gumbel variables and M E EMG, F, Ú) has structure equations
fa (Pa(V)) (v)) arg max m.. @hh + log (fr Uv))
V, is continuous,
V.
V, is categorical, Il
where 0% are i.i.d. standard Gumbel variables. Let the treatment variables set T (Ti,.... Tay We may give all vertices and Un {U1, ... Une J. an topology ordering (rearrange the subseript if necessary)
-, .un Ti, ..... , Vi((),. ... VYV-nr(() (t)
such that for each directed edge (t), (t)), vertex (t( lies before vertex (t( in the ordering, ensuring that all edges start from vertices that appear early in the order and end at vertices that appear later in the order. put Uo and T at the beginning because they are the root nodes of the intervened model. We denote M Tiik (resp. A (U..T.Ik)) to be the distribution of Uo. T, (t)... (t)() (resp. Uo. T, Vi(t), (t)),, pT MV the distribution of V& given Uo. T, Vi(t), (t))
Let S = Ei lift filloo. Next, we prove that
W (PE.. P (.. & (L 1)W ( 1.. +2KS
AT
(11)
By definition of Wasserstein-1 distance,
T W (U
AT (T..T.I)) sup LE
/ glu,t, u1, ox)d ( (oo.T.I.
sup gElip(1)
glu, 1, U1 v8) duT U.R dpU.
/ 9(u, g(u,t, 1i, vk) di dji
g(u,t,u,,"" ,kk d (w (HT.VO.T,IN-I1 - V...o. ,,,
djp U..
sup 9 (
(1)
glu,t,v, ,.) dut U.. d d -T..TIA-1)
(2)
For (1), if Vv a continuous variable, have
TT f glu, v.,,.... wx) d (VV V...U..T Wv (..T.
= =g (u,,, , fa (pa(v)), uvw)) - u, U1, " fa (pa(ex), uvi)
< </Ir (pa(vx), (aa())),uv.) - fn (pa(vx), uva < S.
(12)
17

---

where we have used the Lipschitz property of in the first inequality. If V& is categorical, let á (pa(ve), uv,)) = (f1,... PPn)) = f (pa(vx), uv)) and p (pa(vx), uvg) = (Pi PPr.) (pa(ve), uv)). we get
/ olu,t, .xk) Uo,,Iaa (..
n: Σ
Σ (o,,,t,v,,.. ,)) glu,t,o,, mn))(pp Du) < K
Ips Pul < K2S, (13)
k=1
where we use l/Velloo & n, & K. For (2), if Vú continuous,
/ g(u, U, ... U2) dp d d - ArT -...I,11--1)
=
= o "k- ",,,,, fo (pa(es), uv.)) d (H P PU..T.IA-1).
T
(14)
Since 9, Sa are Lipschitz continuous functions, (u,, L, U1. uk-1, Su (pa(ve), uvz)) is (L + Lipschitz continuous with respect to (u, L, "1,-" .. , Uk-)). We have
1)-
1, f (u, (u,t, 01, , (pa(e)), D) (MU,,T11:11 -
< (L+1)W (ee)((Toor In (15)
If V4 is categorical,
I agu,t, t,,, g(u,t,z,,.. ,xx) du du (Pb:1,1--1- - -1..T....
Σ pk f slu,t,,... ... k) d ( T -i..T,
1; Since 9, J& T--Lipscitzz continuous functions, g(u,t, , is I-Lipschitz continuous with respect to (u, U1, ".. rk -k-1). 1). We have
Rs
/ t, k) (PU.T PU. LW T (PU....IM-II. P... U...
(16)
Combine 12 12 16), we prove Equation
By induction, one can easily get
W (u lmy my AT U...T. T.i
< (L 1) 1jav-ny -nr (W (uD, T ". (T,,T) + +2K - -22
+
II. + 1j
2K²5 + (L 1)m-- (uTTo.:: P.T.oT))
-
L
Let Let K) = 2K2, max (1+1) (I++)aa--)) and notice that W
iT
w (PM(U)),MM(( pm)( because interventions T = t are the same, get
W (M)) < W (PU..T. U. (... < Co (s+ (PM(U), (.
(17)
18

---

B.3 Proof of results in Section 3.1
Proof of Theorem 2 Recall that the neural network consists of three parts 9 = 93 92 0 and Ô2. タ1 have a separable form, dealing with each coordinate of the input individually. As mentioned before, each coordinate approximates the distribution of one connected component of the support. We first construct ýJ and f2, then use Humbel-Softmnn layer to combine each component together.
To construct the first parts, only need to consider each coordinate individually. For the i-th component C, let 14, = PP,/P((C), where Pc, measure restricted to component C., Under Assumption 4 there exists Lipschitz map 9 H([0, 1]4 CC,)FFL 1]4g C.). By 43 Theorem VIII.I], there exists quantized ReLu network 9 of width W1 and depth ((d))) ) (let [n(n-1]] in
43 Theorem VIII.I],, such that
W (((2)) Mr, P(O < < 1/4 (W,
where U4 are i..d. uniform random variables on [0. 1]. By [53 Theorem 2]. there exist deep ReLu network 2 of width @ (df) and depth L2 such that
( 30 0 (L22110)
Let (b(())
(. 02 (z))
02 (x)) get
11 félloo & (1(122/4f)
Thus, the width of Ø θ (d- d.). Let
(((x) (o) (21), 9 Ne (uNc)) i 1,2, . Rd dj 1. d, 1,... ,Nc,
where No is the number of connected components, By Lemma] 3 we get
W (my, P(g (f.))) w ((0)) # (92) # M4 (6²) P()((U)))
< LW ((9b) -1 ,i, P(O((U)))) + 11gا 92 |cc
0 ( 1/41 + L 2/d
Next, let p4- = P(C,) and the distribution of o (Uk) be nu. then we have P Exe Pklkk By
Lemma 4
we have
Ne
Nc
P&W (m,, (bx) O (WT1// max{d LT 2/ max)dd))
W
P.
PERA
Finally, we analyze the error caused by the Gumbel-Softmax layer. Note that as temperature parameter 0,
+ )
wr
0. One-hot(arg max (G; + log Pt
k= exp((logrt Gx)/T)
i=1.-.Ne
where One-hot(k) is -imdinnnao vector with the k-th coordinate equals to and the remaining coordinates are 0 and G; ~ Gumbel(0, 1) are ii.d. Gumbel distribution. Let n² be the distribution of w By Lemma 6 for 0 < r < 1, we have
W (v v2) < <( log r).
By Lemma 5
W ((V P(( o Φi) (U.))), , (vo, P((i) 0t) (U))))) < 0 logg)).
(18)
Let
Ne
37 (21,
.NNa)
wh
Dk.
IRd. =t (WT. wkrc) a
k=1
19

---

We denote J3 = lim, 93. By Assumption 4 the support is bounded. Thus, 9 and 92 are bounded, i.e. 1l02 (x) < K. Since functions h(w, X) = w is Lipschitz continuous the region |wlll 1, || o0 K, get
W (P(03 82 (Ux)). P(gg Ô2 o (i((U)))) & O Fog 7)
(19)
from 18 Putting things together, we gel
Ne
W (P, P o 92 o 96 (UW)) & W
P.
PaPk
+ + Σ
Pk P(g 92 gi @i(ww))
Nc
W
P
P
+ (P(0) 92 91 (1()))), P(03 92 91 (Ux)))
k=1
+ Wi 1/ max(d])
1.2 2/ max
< 0
7
log
where we use 19
B.4 Proof of results in Section
3.2
Space-fille filliiiiinng Curve
Lipschitz Homeomorphism
Gumbel-Softmax
Figure 8: Architecture of the deep neural network for 4 dimenniiion output. The first (yellow) part approximates the distribution on different connected components using deep ReLu Networks. The remaining two parts are similar to the wide neural network in Figure
Before prove Proposition we need to introduce some important notions. Let {C,,) be sequence of partitions of the unit cube [0, 1ld We say } has property (*) if the following properties are satisfied.
1. Co = --
2. C.+1 = [Ci, dutt li,=u,... 21 is refinement of C, = (Ci,.iz. iin fi.= -2 i.e. Cigsggen,th = U = Ca S.11" Besides, C, is obtained by cutting the unit cube [0, 1]d by planes that are paralleled to the coordinate planes.
The following lemma is important in the construction of Hilbert curve.
Lemma (Algorithm in (25)). Given a sequence of partitions of the unit cube {Ca} that has property (*), there exist a ordering for each partition C.. iee., On {1....,,0 ,ndd] h2d .. in ig 0, ... 2d 1}. such that the following two conclusions hold.
j. 24, the first n digits of On-1(1) are the same as On1 2. Adjacent cubes in the ordering intersect, i.e., Co.(1) O Co.(+11) # Furthermore, Co.(9 n Co.0+11) is a d dimensional cube.
1. If 1).22 <
20

---

Proof of Proposition [1] Without loss of generality, we can assume that P is supported on [0, 1]" vanishes the boundary and P(B) > C))(B) for some constant C > 0 and all measurable sets B E [0, 1ld. Suppose we have proven the conclusion for this case. By Assumption 5 there exists E ((, 1J", Fr 1] K) such that 1 satisfies these conditions. There exists continuous function 7 such that f IP = 7# X, which implies I" = (f +) In particular, if 7 is 1/d-Holder continuous, f is also 1/ //d-Holder continuous because is Lipschitz continuous.
When d 0, the constant map satisfies the requirement. We focus the case d in the following. The proof is to modify the construction of the Hilbert space-filling curve. By changing the velocity of the curve, the push-fot mush-forward measure of the Hilbert space-filling curve can simulate great number of distributions. We use À to represent the Lebesgue measure [0, 1].
The construction of f is inspired by the famous Hilbert space-filling curve 28 To illustrate the idea, let us first assume that P is absolutely continuous with respect to the Lebesgue measure À and consider d 2. In the k-th step, divide the unit cube into 2 evenly closed cubes C, = (C Czar, , such that C, is a refinement of -
Proof Sketch:
The construction of standard Hilbert curve is to find a sequence of curves 7n that go through all the cubes Cn. The curve 7n has one special property. If ( E Ck,R-1, then 7m (t) E Ck.n-1, Vm > For example, in Figure 9 the points on the curve in the lower-left cubes will stay in the lower-left cubes. Note that #TC),((C,,))
X (7, ( (CR,,)) is the time curve "nn stays in cubes Ck.n. The idea is to change the speed of the curve so that IP and (7n agree on cubes in C., i.c., P(Ck,,,) A (7 (C..,)). Since we assume that IP is absolutely continuous, ,()C).,) = 0 and we don't need to worry about how to divide the mass on the boundary. For example, let the green cubes in the Figure to be Co and suppose that starts from Cg. We will change the speed so that ?1 spends P(Ca) time in this region. In the next step, we divide Co into four colored cubes C2. C4 on the right. We change the speed again to let the time spent in each cube equal to P(C,). Note that this construction preserves the aforementioned property, i.e., for E [o, P(Co)), 7n Co Vn > As + co, it can be proven that "hn converges uniformly to curve y. We can also prove that IP and Ty agree on Cn- Given that - Cn generate the standard Borel algebra on [0, 1)2, we can conclude that I >
In the general case, may be absolutely continuous. As result, the boundary may not be F-measure zero. We will need to perturb the cutting planes to ensure their boundaries are measured zero.
Figure 9: The construction of Hilbert curve.
Preparation. For a n-dimensional cube C = IT [a,, bil, the diameter of C' is diam(C) VE (b: az)². We also define the function R that measures the ratio between maximum edge and minimum edge. For collection of cubes C {Ci,.... Cm Cs defined to be
II. [a b.]. R(C) is
R(C)- maxiı lat 1/1
min, la b.9
21

---

R(C) measures the shape of the cubes in collection. We need to control R(C) in the construction to obtain Holder continuity in Step 2.
Step I: Define partition.
First, we construct a sequence of partitions that has the property (*) recursively. Let Co {00, 1] Suppose have defined close cubes collection C.,
fo in 1iy=0.. 12-1, such that
1. C. is obtained by cutting the unit cube [0, 1]4 by planes that are paralleled to the coordinate planes.
2. Ch da-1 U., Chr,ba....k dn and diam (1.,22---n))) & 2/3 diiaddammm diimmaaa, An)-
3. P( (an dnn) = 0 and R(Cn41) & (1+2 R(C,.).
Next, we construct Cx+1 from Cn that preserves these properties. We refine the division C, (o -0, -2--1 by union of hyperplane P.r {y Vi =) to get (C such that Ci Cir,ia in = Ui Ci,,i (in1 and diam Ci,iii.., (n-1)) < 2/3 diam Chipaan (.). By property 1,
C, is obtained by dividing [0, 1]dd using
Pr.rd ... PP.rjan., Parg.'.. " Pa.rg. rá = 0, r2n =
we can further cut the unit cube using hyperplane construction may satisfy property 3, P(aC (2 0. We need perturb each hyperplane to ensure a measure-zero boundary. Since
-1 However, this
Z. = : E [0, 11 [x] =r]) #
at most countable, we can perturb the hyperplanes a little bit, i.e., {P (ritttr) (o(fttr..//++..)) ())//),)))) ) to ensure property 3. In this way, we can choose |e to be sufficiently small such that (a < 2/3 diam (m):
and
maxij ((1)+1 -r²) /2 /2 (e maxi.j (ri+1 r()
miniyj ((r)+1 - r3)) (e.sl) min.,, (+)+1 (1+2-T)
Therefore, R(Cx+1) < (1 + -- ((C,) and is easy to see that properties 1,2,3 are satisfied.
Step 2: Construct Hilbert Curve. By Lemma there exist an sequence of ordering {O,} of (C.) that satisfies
The first n digits of (1) with O,()), (j - 1).24 < &
.Cour1 O Co are dimensional cubes.
Let Io [10,1]} define I, recursively. Suppose we have define interval collection In = {(Tig.o d., 11, such that Tig.ig..,,, = Ui Innigg.. in and P(C 3.) 1Tr,igr-- Since P(AC )n-1) = 0, we have P(C = Eint. P(Cin,srr-dht) With the ordering, we divide each Io,, E 2nd into 2dd closed sub sub-interval (0.)) < i-1 k== Pk. Ein Pk] where = PCCo,, (1()). This construction satisfies (oo, P(Co, Note that by condition in step 1, P vanishes at the boundary of the cubes. Therefore.
(j + 1)2d such that Io, 12i=
12"
12"
Voo.00l = =P(Co..)) =
Σ
P(Co =
Σ
(20)
1)2811
)=(1-1)244
Now, we can construct a piecewise linear function 1 such that
(In+1) (Co.))&(CCo...// = IP(oo.,(0)) (1m+1) ((0Co..101) ( Vi.
(21)
22

---

The idea is to construct piecewise linear curve going through all cubes in Cu+1 exactly once and modify its speed. Take 2o Center Coo,, Center(Co... (24(+ where Center (at, b,]) ((a, + b,)/2) 1),,, & is the center of cube. is well-defined since (0.+1 O (i+1) are cubes of dimension d - 1 by Lemma [ One
02 Conter(Co.,ta n Co. U2ain+1) e (1)), Co.,,
possible choice of (n+1(() is
2(0+1>e
(1
Pk ))
(1) = 00 +
Σ ==1
(t 11-1)
Σ k=
ps
(22)
The first two curves 71, 72 are shown in Figure 9
It is straightforward to verify that
bn+1 (Ei=1 Pk) = 02 and
io+1 (To m--1
Σ Pk. Σ
pkl) C Co..1()
1= 1=1
In fact, since 1; 8s are on different surfaces of the cube Co. the line segment between Wi-1, vi lies inside the interior of Con+1(1) and 7n+ goes through all the cubes Co.+1(1) ex-
actly once. We have Tx (Im(Co.+1(0)) C |_ Pk: Ex= Ps. and (I=+1) ((Com) (1) P(Co..1(0)) where Int(-) is the interior of a set. Besides, we also have (7x+1) (13
&
O.
Finally, for any kn > li2 2 n, E 1), by property in step 1. 20 and 22
Yk, (1): 782 (1) are in
one cube Cay.ia...Kk.. .... and diam( C2, (.) < (3)) Vd. Thus, likk (t) Yk, (t) < (3) vd which
implies (m)( converges uniformly to one continuous function 7())
Step 3: Verify Conclusion P = Tm A. By W (((n) 7, 7) & 11 - 700 - 0, (7x) q converges
weakly to 7. By construction, PPOC f1..2--... dn)) = and (7m) (CC)))(CCoooo (C .tm) P(C ) Therefore, by condition 2 in step 1, for any k 3 n.
(7k)
U
Σ
in- dk
Σ
A 1 (Cty
in-1, de
P(C (n) P(C An);
(23)
Pm 1 A
where we use P@aaC 2g
p( sg......)) and (m)) A(8C,, i 3.)) = 0 in the second and the last equation.
We claim that 7 X00, 11.2 (.. = O. For h > n, we define
BB
U
i0 i n fgm in
Let ks hi 2 and B fx: d(x, 00,, ia...
ii....................... 2n) c). have
(rn) (Int((....) < (Tn)
P(BE.) P [B2
VA > ki
where we use (33 and the fact that (7x)4 A vanishes on aC in in the first equality and diam(C,,
(Ci,, ,2.. .ba (2) hy Vd in the last inequality. Let l + co, by Portmanteau Theorem,
we get
< lim IP (((2/3)* va) = =P(B318)tvV
Yy (8 2. & 74 (Int(B,,)) < (
k-400
k
Since k is arbitrary, let Kı 00.
7* X(AC in) & lim P [B(2/3)+1 P(aC (.)..,.........))- =0
400
23

---

and we conclude that 7#X(0Cs ba. (.,) = 0. By Portmanteau Theorem, let k + oo in (23). P P( ...) Let C U C, Notice that for any open Uccu,CEE- C, which means the dallebrra generated by C* contains all Borel sets. Besides, C* is a T-system. Hence, A (U)) = (U)) for all Lebesgue measurable set U.
we obtain Vi vo
U E [0, 1]6.
Step 4: Holder Continuity of y. We verify the condition of 47 Theorem 1]. In and C, in the above construction correspond to developments ork R in 47 Theorem 1J. Define f&& fi(()o())) =
Co2 i = 1. 2nd as map from In to C..
1. By construction, if 1 E I2 E IA-1. C. 12, fu(l1) y fk-1(12).
2. If I2 Is and I 1 + 0, I, 1a are adjacent. By Lemma 1 [T)) share
(d 1)-dimensional boundary. Therefore, (a(Ti) (x(12) # 0.
3. We have |Ca-1l < 1x)
4. By property
n-1
R(C.)) &
II (1+2-*) k=1
II (1+27H) < <c.
k=1
Let A = Th (1 + 2-). We have for any C' E Cu. by Assumption 5
diam (C) & ((C,))(C) & ACT & ACT max (diam(I)),
where C₁ is the constant in Assumption S
5. Since Ia consists of one-dimensional intervals, we have (Ix) = =gap(Ix).
Therefore, 7 is 1/d-Holder continuous.
Proof of Theorem The proof is similar to the proof Theorem The difference is that the first part, we use deep ReLU network to approximate the Holder continuous curve instead of wide ReLU network.
Let μ4 Pc,/P(C,). By Assumption and Assumption for each connected component C₁ of the support, there exists Lipschitz maps Ø H((0, 1 n F 1]44 C.)) such that
( (B > C,N(B)/P(C))
for any measurable set C [0, o By Proposition
| there exist a 1/df 1/df-Holder -Holder continuous curve
[0, + j0, 1]4 such that (nx) f X = (0b) p..
||| 1/d where C is the Holder continuity constant factor), there exists deep ReL.u network / of width and depth L, such that
By 53 Theorem (take wxxx)
| (nn) <0 (I,2/d7)
(0
where (wi is the j-coordinate of n. Let (a)) = 1.. (I), .01 (w)). we get
l %iloo 0 [z, 2/1f)
Thus, the width of of θ (d9). By Lemma 3
w (()) n4 (())( W (G,), ((O < l - miloo (1(11
The rest are the same proof of Theorem 2
24

---

Proof of Corollary ! Suppose that structure equations of M are Vi is continuous,
Ji (Pa(V.), Uv.),
V;
I| =1' FIF
aag mej.
99 Vi + log (Ji (Pa(VV)) vv))),
Vi is categorical,
Let de be the input dimension of fú, di be the output dimension.
arg aaggmnneeey MeNN qp (2d) +10) fI. filloo
V, continuous,
m0 arg min REN agn (qt 10) IIf filloc),
V, categorical.
We truncate the neural network at () for categorical variables because the propensity functions are required to be non-negative. This truncate operation will not influence the approximation error since fi are non-negative. According to Assumption 3 fi are Lipschitz continuous. By [53] Theorem 2],
we have, if Vi is continuous, Ilf: - lol & O 1//d"" & O(LO 1/d
If V3 is categorical, let S = |lf (pa(e=), uv.) (pa(ex), uv 1l.0 P f (pa(ek), uv:) = (pa(ex), uv.) /1lfÍl1. If S 1/(2K), ||p x 2KS. If & 1/(22),
1p - &l <
II |lf (pa(ts) uv) - f (pa( (x), uv llo + Illfll - 111lfl
ll
(n4 S $ (n: + 1)
S & 2(K + 1)8
|
where we use Assumption that n. < K and $ < 12K). Thus,
[| - ft/llfillaloo & O(Ils - -illss) <0T max
By Theorem there exists neural network وJ with architecture in Theorem 3 such that W(P(U,), P(G (2,))) < (1,22
2/d" + Tog
2/d
-T--logg llg
where Zj ~ ([0, 1] No>)>) iid., No.; is the number of connected components of support of U,, d' is the dimension of latent variables Uj and L1, L2, are hyperparameters of the neural network defined in Theorem Let U, (2,)) By Lemma
W (PP(U,, (Un))) P(O,, ... (nw))) (( <0
(1
2/d"
Lb
2/15
(r rlogT)
Let M be the casual model with the following structure equations
ja (Pa(V)). (Z,,))))) eUvv))
Vi is continuous,
arg maxaaakelnj {9x + log (fr (Pa(Vi), (0,(Ze,))o, (v.)))
Vi is categorical.
By Theorem
I we get (pmr (V(t)), PV(t), 00
Σ fello +
Σ
Il - ftllfill
Vi contimuous
Vi categorical
+ WP(UU,, ... ,Unn); P(Ū1,.... (ng)))
O 2/ + I,y
2/
2//6 + (T + rlogr)),
+ Tog
for any intervention T
C Proof of Consistency
C.1 Inconsistent Counterexample (Proposition 2
Proposition 5. There exists constant and SCM M satisfying Assumptions 7 with a backdoor causal graph such that there is no unobserved confounding in M For any c > O, there exists an SCM Me with the same causal graph such that W W(PM (V), PMM (V)) S c and
LATE ATE M.
25

---

Proof. Let V = (X,T.Y) be the covariate, treatment and outcome respectively. T is binary variable. Let structure equations of causal model Mg be
w.p. 1/2
= 0
w.p. 1/4
8
w.p. 1/4,
11/2
2 = -ror0,
P(T = 1|X = x)
(3/4 , = 6
[ + Uy <<0
Y
(x/6 + Uy
where latent variables are independent and U, mean- zero noise. The distribution of Ma
Yx, 1, pu, pu,(yy) (v)/8, Px.r,y (0,0, PU; (v)/8 (6, 3pc, (y 1)/16, P (6,0, pu; (y 1)/16. Px,,y(-1,1,)) = Pu, (y - (-1,, -P (v)/4.
As distribution of MM 1 _M,, where structure equations of MM'
P(U = 1) = 3/5, P(U = 0) 2/5, P(U2 1) = 1/3, P(U 0) 2/3,
-1 w.p. 1.pp1/22
X
00 w.p. 1/2,
[1/2 =I1
P(T 1| =
5/8 ,
(T+ Uy X = =1 U1 + U,
Y
X = 0, =1
U2 + Ug
X 0, T = 0,
where U1, U2 Uy are independent. The distribution of MM is
Px.r, (0,1,y) = (v)/8)/8 + 3pu, (y 1)/16,
(0,0,0 = Pu, (v)/8 1 pu, (y 1)/16,
Px,r,( (-1,1, = -v 1)/4,
-
(-1,,, = -U, (v)/4.
Some calculation gives W(PM (V), pMb (V)) & 8/2. It is easy to calculate the ATE of the two models.
is easy see that M satisfies Assumption
ATEM 19/30, ATEM, = 1/2.
This example implies that even the Wasserstein distance between PM' (V), /MM(...VV. converges to zero, their ATEs do not change. As mentioned the main body, this problem caused by the violation of Lipschitz continuity assumption for Ms. Note that in Ms. [[Y|X,T] X/8. As + 0, the Lipschitz constant explodes.
This problem may also arise in 6 the distribution ball B, = {M: :PMM ,.M").M)) < an) includes small ball around the true distribution S. {M W(PM (MM)) e) C B, and the NCM is expressive enough to approximate all the SCMs the Sc, this example tells us the confidence interval may not shrink to one point sample size increases to infinity even if the model identifiable.
C.2 Proof of Theorem
To prove Theorem we will need the following proposition.
26

---

Proposition 6. Given metric space (M, d) and sets θ C 2 C C C.. C 20 C M. where
0x = == On positive sequences {en JnEN. fnnINEN such that lim = limn-+00 Tn
lim on and continuous functions f. 20 - IR, suppose that
1. 2 is compact.
2. On satisfies
l19n (61) 9n < Lyd(01, 82) + Tn. 00,,02 E
(24)
and su (0))(0) g(0) < 8n In 3 O.
3. There exists a compact subset 2, C r such that for any Og E θxx there exists E O such that d(0, 0o) & tn-
Consider the following optimization problems:
min f()), 8EB.
s.t. (o( & Lgen + on:
(25)
min ʃ(0), 8E
s.1. (0)) = 0.
(26)
and
min f(0),
θ
s.t. g(0) =
(27)
We assume that the feasible region of 26 and (7 are nonempty. Let fūs f 25
f" be the minimal of 26 and (27) respectively. Then, lim in fū, lilliiupppsa fül fm).
Proof of Proposition 6 By compactness of Oxx and θ... the minimizers of (6 and 27 are achiev-
able insider these two sets. Let 0" E 0 Ør E @. be the minimizer of (26) and 27 We first prove
that lim supn-xoc fi & f Note that by (24). the limiting function is L, Lipschitz. By condition
3, there exist On E o, such that d (0n, 0"
< Gn- Note that
gn(On) & lg(0)) In (0)) l9(0n) < 6n + Lyd (fn. 8*) & 8n + Lgen-
+1g
Therefore, 0, is feasible point of 25 (0-) ft
We have lim supn fü < lim sup, f(0m) =
Next, argue that lim oo > f" If this equation does not hold, there exists 0 and subsequence (frx) Jree such that f f vk E N. By compactness of O for each k, there exists subsequence 0% E Or such that 0% satisfies constraint of (25) and f = f (0%g). By compactness, (0r, KEN has a converging subseqence. Without loss of generality, we may assume that (0:,) JEN converges to 0 Ox. Since Ob converge uniformly to g.
lim Ok (0",) lim Igk (0"..) - 9 (0%, (0% (0*) < lim O% = 0. 10000
1000
k
H is a feasible point of Equation 26 Since f is continuous on 
s (0))
lim f (0%x.) & l
k0000
which leads to contradiction.
27

---

Proof of Theorem 4 We begin by defining proper metric space. By Assumption 3 all random variables are bounded. Suppose that max,,; (llV [|m K. A canonical causal model M FE, is decided by
8 = (fi : P(U1), .. P(Un)))
where fü are functions in the structure equations (3) and U, are uniform parts of the latent variables.
We denote M to be the SCM represented by 6, the underlying SCM be M and pe to be the distribution of M We consider the space
M = Fv. x ... x Fvan x P (1-K, ... ...KK())...PP((( ...XP(IKKK
where
F (I-K, K] I-K, (KK,
Vi continuous,
Fv: =
[f:llfll= = 1.f (I-K, II-KK,,,,KKK,,,KKK [-K, K)(lm)
V categorical,
dy d out are the input and output dimensions of fi.
F =f 11flloo < K, Lipschitz continuous}
and P(K) is the probability space on K. For 0 (f1,... ,.nv, P(U1), P(Uno)) (fi Say. P(U(), PPU )). define metric on M
ny
d(0,0 0) Σ - fall Σ
W(P(US).
Theorem D states that the Wasserstein distance between two causal models is Lipschitz with respect to metric d. Now, we define O,, Let
P, P(U): : U is the latent distribution of A NCMg Fi, F2,m:
mm) F2m::
In other words, Pn contains all the push-forward measures of the uniform distribution by neural networks. We denote O, Fvi. ... X Fvay X xP where
Foxm : Fo.))
V, continuous,
fv..
V; categorical,
and Fo,n is defined in Theorem 4 Note that by construction, latent variables are independent and Pa can be decomposed into direct produce Pn,1 ... x Pn.ng. Let
x. = U On, In (0) = SxA, p (V), P (V)) f(0) = =Eipp, EM (F(V ... ...
Vay (t))
and θx (0*). Note that f() is continuous function since by Theorem 1 and the fact that F is Lispchitz continuous,
[f(0) f(0')) & Er (v)), (V)(())
E E =
Now, we verify the conditions in Proposition
1. By Arzelà-Ascoli theorem, FK (I-K, [-K, KY precompact set with re- spect to the infinity norm in space of continuous functions. And thus Fy, are compact sets.
Since measures in P (I-K, K4 are tight, P (I-K,
compact with respect to weak topology by Prokhorov's theorem. And the Wasserstein distance metricizes the weak topology. Thus, (I-K, are compact and the space (M, d) compact space. Closed set Oge M is also compact.
28

---

2. By definition of In-
(nn(0) 9n((0)) = SSan ( (V), m. (V)) - Sxn (PS² (V), m. (1)
W ph (V): p (V) W (PH (V), Pm (V)) + 4(log(mm) + 1)An
W (P (V), P (V) + (llg(mmn) + 1)hn
< O(d(0, + 4(1 + log(nm,.))>.
where we use Lemma 7 in the second inequality and triangle inequality and Theorem ! in the third inequality. By the condition in Theorem 4 the second term (1 + ) + as n + d0. Therefore, 24 is verified with 4(1 + (og()m,)) )m
We then verify the uniform convergence of Jn. By triangle inequality,
(9n( g(0) SSS..
[P (V), P (V)) W (PTT (V), (o(
< SSS,.. ph (V), pe (V)) W (P8" (V), P (V)
+ I (PH (V), p (V)) w (1"0 (V) (V) pe (()))
By Lemma 7
SSn, (Pa (V), P (V)) - W (Po (V), Pm (V)) | < 2(log(mm) + 1)t0
and we get
g0) g(0) < (llg(m))) 1)dn + W (P (V). P (V)) M (iT (V), (V):
+ +| PM (V), PM (V)) -w W (po
(V),
< 2(lg((mn) + 1)A, + W (P m.
+ +W(P (V), p8 (V)) (U), pe (U)))
< 2(log(mm) + 1) + 0 (PM (U), pd" (U)) +W (PS(U),
(28)
where we use Theorem Din the last inequality. We first bound sup,, W (U), p (U)) using standard VC dimension argument. Note that (UI, Uny } are independent. By Lemma 5
ny
W (P), mn (U)
W (PO (U)), PM (U.))
(29)
By the construction in Theorem 3
(U.) EjENNe.) P(So,, (Ziz)), Zig
Unif(O, 1), where fe.,, are neural networks with constant width and depth Li, + L2, Nc,; is the number of connected components of (PU.)) and 02, are the parameters of the neural networks. By Lemma 4
sup W (P (U.), P ma (U:) < 0 max sup W (P (Zra)), Pm.. (2is))) JE[No.l 8.,
By (6). the pseudo-dimension of NN L) is O (L log L). By boundness of all the neural networks and Lemma with probability at least
1-exp (o ((c.) ((e))-dim
di log(<,) + (Ln,1 + Ln log(L + Ln.z)log c, mn
the following event happens.
sup W (P((o., (Zr,)), Pmm, (fo., (Zr,)) & en + En
0:.
NNot that we truncate the neural network to ensure boundness in Theorem This extra truncate operation
max{- KK, min{ (K, f}} can be viewed two extra ReLu layers, so Lemma 8 still applicable.
29

---

Let
11/( log Mn, L, mn
Lanzz (20mert logm mn Cn Cmn
-1((omext)) log mn
" = mp
with constant C' 0 sufficiently large, we get
-2/(S +2) log log mn ))>1)) -1
sup (Z.)), Pm.. (fe.., (Z),))) <0 mn O
As long = (()), the Borel-Cantelli lemma implies that almost surely, there exists N such that when n N, supa,, ((P(fe,,(Zz))) Pm.. (Z())) &
O -1/(d +2) log mm for all i,j. Therefore, almost surely, for sufficiently large n,
-1/(d +2) log mn
sup W (P" (U.), P (U)) & <0 mhn
(30)
17 Theorem 2] shows that for sufficiently large if 8n Cin 11/pm1/mxxxxxlll max{[ (c (n)) where C1 is a constant,
[exp(- CC lo))
d
P(W(P" (Ut), Ph (U.) 6n) <
-CO, log
exp
(2+ ( n2/2 (nn)
Expp(CCCs log 1og2/dmmn (n))
du max
2,
where C > is constant, Let C1 sufficiently large such that
P(W(P" (U.), (U.)) > 8n) & (0
Therefore, En=1 P(W(Pe' (U:), Po (U.)) > 6n) < xc. By Borel-Cantelli lemma, with
probability 1, there exist > O such that W(P" (Uz), P. (Ut)) & on, An > N. By
Equation 29 with probability 1, there exist N > 0 such that
W(P" (U), (U)) & (66)), Vn N.
(31)
Therefore, by Equations
28
30 and 31 almost surely, the following inequality holds
eventually,
-1/(dmnatt) +2)
sup (0) -(0) < 0 log(nn,,)),, + 5,, mn. 0e
log mn
8n
where 8, is defined in Theorem
3.
Proposition 1] shows that given I--Lipschitz continuous function f [0. 11 - R. there exist f e NW m. (W, ((log(m)) such that - O (W-1/d) and f is vmL- Lipschitz continuous. For a multivariate function with output dimension m' we can approximate each coordinate individually and get a neural network approximation f that is Vmm' L-Lisshhi continuous and ||f - fll & O (W-1/m).
133
( Next, define the truncate operator TkJ min K, max{- K, {}}, which is contrac- tion mapping, and prove that applying the truncate operator will not increase approximation error. If [|| < K, have
|lf Tx fl
-aafTTkflle < 1f fll & O (w-1/m/)
"The original proof does not specify the depth of the neural network. The authors show the network architectures can be chosen as consisting of O(W) parallel blocks each having the same architecture, Each block is used to realize the function
((x) (uiu(minn(rs Nigks
+ 1), minn1 (1 + wx), miju( ra))) EER.
This function be realized by feed-forwar network with width O (m?) and depth Ollogm).
30

---

Therefore, we get that
| Í1lo & <0 (Wo.r//m)) (32)
sup
inf
fENN fee F s. (Wo.n (log m))
Theorem implies that for each latent variable Us, there exist neural network 9i with architecture in Corollary such that
((P())),P(a(()))) & 2 L 2/dmax
L
+ Tn
log Tn)).
==1
By Assumption we know |oo & K, which implies
a
2/ im
& ((((U))) 0
L
+ Ta(l - log Tn)).
(33)
Combining Equations (32 and 33 with the same proof as Corollary the same way Corollary |
it can be proven in
Ihhat there exists a 0₂ E O, satisfying
d(0",0m) En (Wo-k/d
1/d
+ _ 22/
+ 22,0
22/4 mon
(1-1- log-logr Trl
Let Ox {0*} we have verified the third assumption in Proposition
Take the Wasserstein radius to be an Osn + Cn), Proposition 6 implies the conclusion.
C.3 Proof of Proposition 3
Lemma 2. Let (T,8) p, (T.Y) v and suppose that f(t) = EY) B, 17 are
L-Lipschitz continuous and [f(t)] k(t)(t) < K. then we have
[((ee -
< Ow,(m,))
where Ow 4LK + 2K 11.
Proof of Lemma 2
By the duality formulation of Wasserstein-1 distance, we have
W(,,v)
sup Ey 8)] ETT, sELip(1)
get (f(t)- we verify go is a Lipschitz Lipschitz.contimuunu continuous function in ((t.g) 1(t,,))l < K}.
19u(t1. (1)1..1)= - gu(t2. v2)1 < 1gu(t2, v1) - (u w2)1 + (gu (2) - (t(2
= [(f(11) - ((4)) 12) lo2 s(h) (f(12) - f(12)))
2K y1 y2l + (()
2K y1 y2l + 2KT/41 12/-
Let Lg = 2K max 1}, we have proven that go - continuuus in ((t,)) (tl, <
K}. Thus,
W(,,v) >
[E,[go (T, 8)] E, (T,
Lg
1
(BA((((T) )( e] - -E((((T) ((T)) = +])
Ing
1
(Bu((f(T) - -(()) - - ((T))((T))
(34)
Lg
31

---

Now, let h(t) = (f(t) f(t))(tt. Following the same argument, it can be proven that h(t) is Lipschitz continuous with Lipschitz constant being L 4LK. Hence,
Ealh(T)) > Ex(h(T) - (.,(
Plug into (4). and we get
(Lg + (n) > -
=E
- (
Proof of Proposition 3
If Y is not descendant of T, E|Y (t) E[y] and we have
(E) - E (t))) dt 1,² [Em[Y]-Ba EM d
( (t) Em(lT) < (tz WP) PM(())
Now, suppose that Y is descendant of T. Let X = Pa(T). Note that [y(a,, () = BM x, T t| is Ly-Lipschitz continuous with Lipschitz constant L, < (L (L+11 1)TM This is because Y can be written as Y = Fo(X, U2) where U, are latent variables independent of T' and Fo is composition of fi in structure equations. The composition of Lipschitz functions is still Lipschitz and Fo is composition of at most ny L-Lipschitz functions. Fb is (L + -ipsschtz and is fy t) Eu, , (Fo (X. T, Uy) Recall that v, μ are the observation distributions of M and M respectively in Proposition 3 Similarly, fy(x, t) = E E = T t) is Lyg -ipssiischiz continuous. By Lemma a and the overlap assumption, we have
Ow W Ww, > EEW [V - ( (((X,T))
= -
8 I.a [(saeet)) fcr,t (g.
8 1.a (f fo (sle,))((a))) P(dt).
Note that (z, 1) is Lipschitz continuous, we have
If fule, - / (alett)(ddo) & Ly ((,W()
Therefore,
(/ (u(es)))(d)) / (olo))p(dss)
> 2 (( / Pu Dra(aa))
- -(filee / f folle)))(an))
3/2 (/ (ole, - fo (ola))))(at))) 2 (BM ((0) - ExT(((1)) 13W2
1
-L. L. (H,
2
Combine all the equations, we get
1 (EM ( &
2Cw W(p,v) (2, -t).
8
32

---

Proof of Corollary 2 In the proof of Theorem we know with probability at least 1 - O(n 2), (6)
has feasible solutions and
W(P (V), (V)) & O(an), W(P
min (V), p0n (V)) & O(an),
where notations and pe are defined in the proof of Theorem and On is one of the minimizers of ( By Lemma 7
we know that
W(P, (V), per, (V)) & Shm (Pa (V), (V)) + 2(log(m,nn) + 1)An & O(an).
We get that
W(PM (V), Pb, (V) W(PM (V), (V)) (M (V)( (V), O(ax).
By Proposition
we get Pr - F.I & O(van))
D Experiments
The structure equations of the generative models are (5). We use three-layer feed-forward neural networks with width 128 for each f. and six-layer neural networks with width 128 for each õy- We the Augmented Lagrangian Multiplier (ALM) method to solve the optimization problems in 3 We run 600 epochs and use a batch size 2048 each epoch. my set to be m, = n. The "geomloss" package [16] is used calculate the Sinkhorn distance. To impose Lipschitz regularization, we use the technique from [23] to do layer-wise normalization to the weight matrices with respect to infinity norm. The upper bound of the Lipschitz constant in each layer is set be 8. The t in the Gumbel-softmax layer is set to be O.
For the choice of Wasserstein ball radius ans 3.4]. We can take the criterion function in [II] to be Q(0) W(PM (V), pM' (V)) and its empirical estimation to be (0) = W ((P.vt (V), P. (V)). In the first step, we minimize the Wasserstein distance 0; arg min& W(P.M" (V), P.M (V)). Then, [II] propose to refine the ra- dius Qn (0;) by taking the quantile of subsample (0)::. (O), where Q2 denotes the criterion function estimated at j-th subsample of size However, it cons-minn to solve the radius an be the 95% quantile this optimization problem many times. In practice,
the subsampling technique from ||] Section
of {W (W, (V),, P.Mz (V)), where we use 50 subsamples P,M' .J = 1, 50 from (V, with size [15/n]-
D.1 Discrete IV 14
We consider the noncompliance binary IV example in 114 Section D. J. The causal graph is shown Figure TO] We could see from Table [ that the bound given by NCM slightly worse than Autobounds but is still close the optimal bound. Besides, the Autobounds bound does cover the optimal bound in this example.
U
Y
Figure 10: Instrumental Variable (IV) graph. Z is the instrumental variable, T' is the treatment and Y
the outcome.
33

---

Algorithm
Average Bound
SD length
Optimal Bound
True Value
NCM (Ours)
[-0449.0005]
0.05
[-0.45, -0.04]
-0.31
Autobounds ((14)
[-.45,-0..05]
0.02
[-0.45, -0.04]
-0.31
Table 2: The sample size taken be 5000. We average over 10 runs with different random seeds.
SD short for the standard derivation.
D.2 Continuous IV
Now, we turn to the continuous IV setting, where T still binary, but and can be continuous. Let E ~ XZ1 + A-)unf((-11 where Z1 is the Gaussian variable conditioning on [-1, 1] and the structure equations of MM to be
Fy U= P2 7 Fly:
P(T = 1[) = (1.5 Z 0.5
Y = 37 1.5TU + U Ey,
where F are independent. is easy to see the ATE of this model is 3 regardless of In the experiment, randomly choose ten À ~ Unif(O, 1). For each A, we run the algorithms 5 times to get the bound. We choose different latent distributions (indexed by A) the experiments to create more difficulty.
Since Autobounds can only deal with discrete variables, we discretize and Y. Suppose that Z E [1. ul, we map all points in intervals [[+ - l)kk, + (í (u- 0, 0.1.-.... 1....... k to the middle point + (i + 1/2) l)/k. We choose k 8 the following experiments. The choice will give rise to polynomial programming problems with 2 decision variables, which is quite large.
Table Jable demonsttatee the results. While both algorithms cover the ATE well, gives much tighter bounds on average. The main reason may be that the discretized problem does not approximate the original problem well enough. It is possible that a larger discretized parameter can give better bound, but since the size of the polynomial problem grows exponentially with k, the optimization problem may be intractable for large k. On the contrary, NCM does not suffer from computational difficulties.
see that NCM
Algorithm
Average Bound
SD of length
Success Rate
True Value
NCM (Ours)
[2.49.3.24]
0.49
50/50
3
Autobounds (14))
[1.40, 3.48]
0.26
50/50
3
Table 3: We take sample size of 5000. We randomly choose 10 X ~ Unif and get 10 models
M For each model M we run the two algorithms for 5 times. The success rate is the number of times when the obtained bounds cover the true ATE divided by the total number of experiments. SD is short for the standard derivation.
D.3
Counterexample
We test neural causal method the counterexample in Appendix C.I to be the normal variable. The structure equations are
We choose the noise U,
P(U = 1) = 3/5, P(U = 0) = 2/5, P(U2 = 1) = P(U, = 0) = 2/3,
-1 w.p. 1/2,
x=
0 w.p. 1/2,
11/2 I -1,
P 2)
55/8 1 = 0,
T+U
X =1,
Y
U1 UU X = = =1
Un + Un
X = 0'''' =
34

---

We compare the confidence intervals of the unregularized neural casual method and the Lipschitz regularized one under different architectures. We choose the layerwise Lispehitz constants upper bound to be 5 and 1.2. As a benchmark, we also include the bound obtained by the Double Machine Learning estimator using the EconMI. package. The result shown in Appendix D.3 For this identifiable case example, the double MI. estimator produces better bounds for the ATE. The intervals given by regularized and unregularized NCM are similar to the regularized one slightly better in the left figure, where we medium-sized NNs. However, in the right figure, the obtained intervals after regularization are tighter, although slightly biased, compared with the regularized setting. From these two experiments, we conclude that the architecture of NNs will also influence the results and adding regularization during the training process can prevent extreme confidence intervals or inconsistency.
Countrrecipple
Counterexampee
TLe ATT
The 6TF Jnagulerted ncV tepoluiiall NCM Lp 1. Double
10-
0.00
-20
-0.25
582
3.00
2003
1000
2000
3000
Sanp C.5
Figure 11: Comparison of Lipschitz regularized and unregularized neural causal algorithm. The two figures show the results of different architectures. The figure on the left side uses a medium-sizee NN (width 128, depth 3) to approximate each structural function, while the right figure uses extremely small NNs (width 3, depth 1). In all experiments, we use the projected gradient to regularize the weight of the neural network. For each sample size, repeat the experiment 5 times and take the average of the upper (lower) bound.
E Technical Lemmas
Lemma 3. Let μ. f be two measures on compact set K C. Rdd for any measurable functions F, F,F: K + Idd if F is L-Lipschitz continuous, then
W(## F+1i) < L. (1) + + F221x0
Proof. For any 1-Lipschitz function d2 + R,
Ex=Pa - EE Ex A [x( = Ex= F F(X) - Ex~alg F(X) -Exx-llg F(X)) Ex~ply F(X))
+ (Ex~alg o F(X) - Ex~alg F(X))..
Note that for any x, y E IRd
Fl) - g go F(y)) [F(z) F(y)l L|| vll.
Thus, g F is L-Lipschitz continuous and
Ex~ulg F(X)) - Ex~algo F(X) & (W,
(35)
For the second term,
Ex~plg F(X)) Ex~algo f(X)) & Ex F((X)) - go f(X)I]
< Exxa1]1F(X) -F(X)II < <II((X) - (x))
(36)
Combine 35 and 36 have the conclusion.
35

---

Lemma 4. Let pi... Pas Pi,-. .. Pn be measure on R for any P1, PP [0, 1] such that
Ek=1 Pk: 1, we have
W
Σ Am
Σ
pufia
pr
Pa (un,
Proof. For any 1-Lipschitz function f IR + R, we have
[f(X) Ex [f
Σ ph (f(xxmmee((X))
Ex (f())))
7
Pk (14ks
By dual formulation of Wasserstein-1 distance,
Σ
PElik
Pklk
sup f I-Lipcchitz
Ex-DEima [f(X)] Ex-Er= madn (f()
k=1
Pk W (uk,
Lemma 5, Given two measures
11 X @ Mni
fa 2 ... @ Pe have
W(, & W()::A))
1=1
Proof. For any >> let Tyy. be coupling of pk. Pu such that
Ex.Y Yalli] & W (b)) + e.
Then,
(w, < Exio..o. |||X Y
Ex Exarerall I1lx - Y2lli]
W fit) +c.
Let - 0. we get the result.
Lemma (Approximation error of Gumbel--Sotmax layer). Given r > and pl, ...... PP > let nº ~ X = (X....., ,x)) be
exp((log + Gk)/T)
X E exp((logp) Pk + Gk)/T)'
(37)
where Gk ~ exppp=pp - exp( (xx) are i.i.d. standard Gumbel variables. Let p. be the distribution of x = lim X = (XP, ... x)) ".) Then,
W (nT ,0) 2(n 1)T 2n(n 1)e- - -logT.
divide the denominator and numerator in (37 by - Ph- Pk- Let An {(11, In) >E= = We construct a transportation map A, An as follows. T(x ..,) a n-dimensional vector with all zeros except that the i arg maxy zy-th entry being one. If there are multiple coordinates
Proof. Without loss of generality, may assume that Σn Σk=1 Pk 1. Otherwise, n
36

---

that is maximum, we choose the first coordinate and let the remaining coordinate be zero. It is easy verify that T u2² and 1 have the same distribution 36 For any ò > 0, we have
y log
Pk2 PE1
P([Gk, + Po (Gkz + Pk,)) < <5)
exp(- xxp(-x--) -
(exp(-x) - exp(-x))dddy
tog -8 -00
100
28e
exp(- - (oxp(-y))dy 26,
where we have used exp(-xxexppf - exxp(=x) < exp( (xp(-1). Let event Es = [ii j E [x]] |G; - log
(G, + log < 8), we have
P(Es)
+ logp; (G, logp;)) < +
8n(n l)e-
Now, calculate the transportation cost
Exteu [IT 111 & P(Es) IIT - [1]] + P P(E)) Ex [IT - x x"]1|E
Note that [T 1 & 2. For the first term, we have
((F.)) Exr (XT) (x*))x*1111 [&) & 28m(n 1)e-
For second term, under event E5. let kimax - arg max; X,, j = kmax = arg max; Gs)
cxp(( p5 + +;)/TT) E exp((logPM Pk + Gx)/T)
Σ ΣKz exp((lopp + Gk)/T)
exp( (log Pk + Gk)/T)
ktt exp( (log G+)/T)
exp((logP) + G,)/T)
exp((log7* + G (log + G,))/r)
(n 1) exp(-6/T).
If j # kmaxx have
exp((logp; + G2)/T)
< <xxp(logp) + G, (log Pmax Gmax)))/T) & exp(-8/T).
En exp((logPt Pk Gx)/T)
Therefore,
E Extoyr
< 2(n - exp((-0/7))
We get an upper bound of the transportation cost,
- 1x W (n" .1O) & Ex- (X
2ôn(n - 1)e -1 2(n 1) exp((-81
Let 8 --- -llog T, we get
W (p) ") 2(n 1)7 2n(n 1)e-1 ' log
Lemma 7 (Approximation Error of Sinkhorn distance). For any μ E An, Am and >> 0, we have
< W (i, u) W(, & (log(ma) + 1)},
where -.. the entropy regularized Wasserstein-I distance. Moreover, we have the following estimation of approximation error.
[S}(up)) (H, 2(log(mm)) + 1)A.
37

---

Proof. Let h(T) = -- n,
Lij=1 Tij log T3 + 1, by [3] Proposition 1], we have
0 < W (1, v) - W (M, v) & ct,
(38)
where max (h(T): transportation plan T is achieve optimal loss W w), Since TVy E [0, and f(x) = - log x is concave, we have
m.m
h(T) mm
To log Tıj +
1,=1
1
1
-um
Ti
log
Σ
Tij
+1
717
Yum
5,==1
s,j=1
=1+ +1loogremm)
By definition of Sinkhorn distance,
Sx(u,)) = WI,,(M, Wi,a(,,)/ Wi,,(1, v1/2.
By 38
we get
[SX(u,D) W(H,2)) & 2(log(mn) + 1)A.
Lemma 8. Given measure P on Rd and real function class FF with output dimen-
sion d, suppose that the pseudo-dimension of F less than dF oo and there exists
K > 0 such that [f(x)] K,Yf E F, E Rd then with probability at least exp (O (5- log (5-1) dr log c (-n-=)))) nn))),
sup W W(f#,, ffHN) & tō+e fEF
for all ô,e O. where pa is the empirical distribution of μ.
Proof.
By the dual formulation of the Wasserstein distance, sup Ex~u, [h f(X) Ex (()]) [(X)]-
sup sup W Wr Sppa) (E JEF
We define
N1(c,F,n)) = sup (ef.((((11))) ... f(x)) : f E F)}. (1-11l11)) l11):
where NN,,, S, Ih) is the covering number of set S in é norm. Obviously, if h is I-Lipschitz,
(i h F, n) & (c,
By Theorem 18.4 in 2 for any fixed h,
2e dr
Ni(s,hoF,n) Ni(ee,F & e(d= +
By Theorem 17.1 in 22
P sup EEF
Ex
[h f(X)) Ex ( >1
< exp (0 (dy log co ncc)).
Let Hss be the 5-net of the set H {h h E Fi (I-K, KJo, [-K, K1²) M(0) 0)in loo norm. By Lemma 6 in (11.
|Hsl < cxp (0 (8 1)))
Therefore, with probability no more than exp (0 (8 log 8~ + dr -
sup Ex Ib f(X) Ex ( s(x)( >6
KE
Notice that sup NEH.
Ex-pa [h f(X)] Ex o 28 +
sup
Expun [h o f(X)] Ex f(X)),
hEF
which implies that with probability no more than exp (0 (8 log 8-1 + dr loge nE?))
sup kEH,JEF
Ex-r,, f(X)) Ex-, 4 [(X) 28
38

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We accurately summarize our contributions 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as 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:
We mention some limitations as future directions in the conclusion section.
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 separate "Limitations" section in 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
39

---

Justification:
All assumptions and detailed proof are given.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide all implementation details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 all 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 clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, 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 to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
40

---

Answer: [Yes]
Justification:
We provide all implementation details in the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.. cc/
publ ic quides Codeeubmme ss ssionns aasionooliio icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 //nips. cc/ pwublic/guidesn / //odiddee/Coeeeeeeee Cooeeeooeeeeeeee SudeSuumiiee wwwmissssiii ssssnooliccyyyyoco for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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:
We provide all implementation details in the appendix.
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the confidence interval.
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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
41

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors 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 out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide all implementation details in the appendix.
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, or 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
Answer: [Yes]
Justification:
We have reviewed the Code.
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 a 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 is theoretical work.
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 improvement in the quality of generative models could be used to
42

---

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 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 or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a 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 is theoretical work.
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 to 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: [NA]
Justification:
This is a theoretical work.
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 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 (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssw hopersswiccoe com/ dataset 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
43

---

Answer: [NA]
Justification:Thi is theoretical work.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part 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 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. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 NeurIPS Code of Ethics, workers involved in data collection, curation, or 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 to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to 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.
44


Reviews:
[{"review_id": "1pLNn7PZ2z", "reviewer": "Reviewer_zYjd", "summary": "This paper develop consistency results for partial identification via neural causal model with both continuous and categorical variables. Their results shed light on the impact of the neural network architecture and Lipschitz regularization during training. The resulting method can be trained via gradient-based optimization algorithms, and is validated on synthetic data.", "questions": "- A conclusion section does not seem to be provided.\n- It would enrich the paper to briefly discuss the connection with optimization-based approaches in causal learning (many of which also used similar techniques including augmented Lagrangian and gumbel techniques), although the task is not completely the same (see e.g. https://arxiv.org/abs/2007.01754, https://arxiv.org/abs/1910.08527, https://openreview.net/forum?id=HsSLdHuAmnY).\n- It would be helpful to elaborate more on the assumptions required and discuss some examples where the assumptions are satisfied/violated.\n- Other related work that could be worth mentioning: https://arxiv.org/abs/2105.12891", "limitations": "The limitations have not been well discussed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is clearly written. The assumptions used are clearly stated.\n- The identification result is useful and a good complement to existing ones, by making them more general.\n- The identification result and algorithm are technically sound.", "weaknesses": "- The empirical validation of the algorithm/result is not extensive, but I understand that the goal of the work is to establish identification results and a thorough empirical study might not be necessary.\n- The paper would benefit from giving some proof sketches (or a brief overview of the proof strategy) in the main paper.\n- Many of the assumptions and results are not well explained, making it not straightforward to understand the assumptions and implications of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your advice to improve our paper! Below is our response. We hope our clarification can solve your problem.\n\n***1. The empirical validation of the algorithm/result is not extensive.***\n\nThank you for your feedback. As we point out in the paper, the methodology that we analyze has been proposed and analyzed experimentally in prior work [2,3,4]. The main contribution of our paper is to provide a theoretical justification of this methodology in general environments. Given the prior experimental validation we did not perform extensive experiments and we opted to perform a small set of targeted experiments that highlight the key design elements of the procedure (e.g. neural architecture, Lipschitz regularization) that our theory predicts are important. Moreover, we note that unlike prior work, our work is the first to compare experimentally the neural-causal approach to the polynomial programming approach of [5], which is a key contender in the prior literature in partial identification in econometrics and statistics (see Appendix D for more details on our experimental setup). \n\n\n***2. The paper would benefit from giving some proof sketches (or a brief overview of the proof strategy) in the main paper.***\n\nThanks for your suggestion. We will add some proof sketches in the main body and before the proof in the appendix. Here, we briefly discuss our proving strategy of the main consistency theorem (Theorem 4). \n\nWe first establish a general result concerning the convergence of the optimal values of a sequence of optimization problems (Proposition 6). More specifically, we consider a sequence of constrained optimization problems $\\\\{P_n\\\\}$. We prove that if the objective and constrained functions satisfy some regularity assumptions (i.e. Lipschitz), the domain is compact, and the sequence of constrained functions converges uniformly to a function, the upper limit and lower limit of the sequence of optimal values can be bounded. Then, apply Proposition 6 to this setting, verifying the partial identification problem satisfies the assumptions of the proposition using previous approximation results (Theorem 1,2,3 and Corollary 1). \n\n***3. A conclusion section does not seem to be provided.***\n\nThanks for the feedback. We did not include it to avoid some repetition given space constraints, but we will add it for the camera-ready version. The conclusion we plan to add in the final version is shown in the response of reviewer 8521 item 4.\n\n***4. It would be helpful to elaborate more on the assumptions required and discuss some examples where the assumptions are satisfied/violated.***\n\nThank you for your advice. We will include extra discussions on the assumptions we use in the later version. Here, we briefly discuss the assumptions we use. \n\nAssumption 1 is about the independence of latent variables, which is also used in  [1,2]. Using this assumption, we can model confounding between two observed nodes in a causal model by letting one latent variable affect both nodes. This is primarily a convention and does not limit the applicability of the result.\n\nAssumption 2: We discuss Assumption 2 in the reply to reviewer VZrh. Please see the item 1 of our response there. \n\nAssumption 3 is about the boundedness and Lipshictz continuity of the structural functions, which is quite standard in the literature on representation theorems of non-parametric functions with neural networks.\n\nAssumption 4 and Assumption 5 are about the latent distribution. These two assumptions enable us to approximate the latent distribution by pushing forward uniform and Gumbel variables. These assumptions may be violated if the support of the latent distribution has infinitely many connected components or if at least one component of the support is not homomorphic to the unit cube. However, we expect most natural distributions to obey these assumptions, as a violation of these assumptions can be viewed as a form of pathological distribution.\n\n\n***5. Mention other related works.***\n\nWe appreciate the reviewer’s effort to improve our paper. The provided literature is really helpful. We will add these works to our Related Work part in the camera-ready version.  \t\n\n\n[1]Zhang, Junzhe, Elias Bareinboim, and Jin Tian. \"Partial identification of counterfactual distributions.\" (2021).\n\n[2] Xia, Kevin, et al. \"The causal-neural connection: Expressiveness, learnability, and inference.\" Advances in Neural Information Processing Systems 34 (2021): 10823-10836.\n\t\n[3] Balazadeh Meresht, Vahid, Vasilis Syrgkanis, and Rahul G. Krishnan. \"Partial identification of treatment effects with implicit generative models.\" Advances in Neural Information Processing Systems 35 (2022): 22816-22829.\n\t\n[4] Hu, Yaowei, et al. \"A generative adversarial framework for bounding confounded causal effects.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 13. 2021.\n\t\n[5]  Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, and Ilya Shpitser. An automated approach to causal inference in discrete settings, September 2021", "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": "CGaaLHCPF4", "reviewer": "Reviewer_8521", "summary": "The paper extends neural causal models (NCMs) to the continuous and mixed-type variables. NCMs is a neural-networks based tool to perform an automated point/partial identification and estimation of causal queries. The authors provided new theoretic results (1) on how to construct a canonical representation of an SCM, (2) on how to approximate it with sufficiently expressive Lipshitz neural networks, and (3) on additional assumptions to perform the consistent identification/estimation of an average treatment effect (ATE) from an arbitrary causal digram and an observational distribution.  The paper provides experimental results for the partial identification of the ATE in the discrete and continuous outcomes settings.", "questions": "I appreciate the provided continuous IV experiment. I wonder, what is the performance of the method in other confounded ATE settings where the ground-truth is available, e.g., a no-assumptions bound for the ATE with hidden confounding?", "limitations": "The authors have fully stated the limitations of their theory.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "To the best of my knowledge, this paper is the first one to advance neural causal models (NCMs) to the mixed-type variables setting. NCMs are a universal tool for general automated partial identification and estimation of causal quantities (a very important problem in causal inference and treatment effect estimation). The theory provided in the paper is very general and extends over simple linear SCMs. The paper is clearly written (as far as a massive theoretic contribution allows) and well-structured. The authors rigorous proofs for all the theoretic statements.", "weaknesses": "I didn’t find any major or minor weaknesses in the paper. Yet, I have several suggestions on how to improve the paper’s understandability for the general public of the NeurIPS conference:\n1. I encourage the authors to provide more examples of how to construct canonical representations for some simple SCMs and then the corresponding neural architectures of the NCMs.\n2. I would provide a more precise explanation of Figures 1 and 5, e.g., the number of layers in the yellow and blue blocks. Also, multiple notation elements could potentially be added to the Figures, e.g., the number of connected components in the latent space or the number of confounded components.\n3. I also encourage the authors to provide the code of the proposed method.\n4. Seems like the conclusion is missing in the main part of the text. \n \nI am willing to increase my score if the authors implement the above-mentioned suggestions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the helpful suggestions, which make our paper clearer and more readable. Below are the changes we make.\n\n***1. Provide more examples of how to construct canonical representations for some simple SCMs and then the corresponding neural architectures of the NCMs.***\n\nThanks for the suggestion. We will provide more examples in the appendix in the later version. Specifically, we plan to use the example in Appendix A as an example. \n\nThe causal graph of this example is shown in Figure 2b in our paper. Following the construction in Proposition 4, we use one latent variable for each $C^2$ component. As we explain in Appendix A, this causal model has three $C^2$ components, $ \\\\{V_1,V_2,V_3\\\\}, \\\\{V_3,V_4\\\\}, \\\\{V_4,V_5\\\\} $. In the canonical representation, exactly the latent variables enter their corresponding $C^2$ component. The canonical model is shown in Figure 2(a) in the global response.\n\nNow, we show how to construct the NCM architecture from a canonical representation. As we mentioned in Section 3, we approximate the latent distribution by pushing forward uniform and Gumbel variables. The structure equations of the NCM are \n\\begin{align}\n    &V_1 = f^{\\theta_1}_1(V_2,g_1^{\\theta_1}(Z_1)),\\\\\\\\\n    &V_2 = f^{\\theta_2}_2(g_1^{\\theta_1}(Z_1)),\\\\\\\\\n    &V_3 = f^{\\theta_2}_3(V_1,V_2,g_1^{\\theta_1}(Z_1),g_2^{\\theta_1}(Z_2)), \\\\\\\\\n    &V_4 = f_4^{\\theta_4}(V_3.g_2^{\\theta_1}(Z_2)),\\\\\\\\\n    &V_5 = f_5^{\\theta_5}(V_4,g_2^{\\theta_3}(Z_3)), \n\\end{align}\nwhere $f_i^{\\theta_i}, g_j^{\\theta_j}$ are neural networks, $Z_i$ are join distribution of independent uniform and Gumbel variables, and $g_j^{\\theta_j}$ has the special architecture described in Section 3.1 and Section 3.2.  Figure 2(b)  in the global response shows the architecture of the NCM. Each in-edge represents an input of a neural net. \n\n\n***2. I would provide a more precise explanation of Figures 1 and 5, e.g., the number of layers in the yellow and blue blocks. Also, multiple notation elements could potentially be added to the Figures, e.g., the number of connected components in the latent space or the number of confounded components.***\n\nThank you for your helpful advice. We have modified figure 1 and 5 according to your advice. We include the figures after modification in the global response PDF. Figure 5 is changed similarly and captions about the number of layers will be added too. We will implement these changes in the later version. \n\n\n***3. I also encourage the authors to provide the code of the proposed method.***\n\nThanks for the suggestion! We will include the link to the code in the camera-ready version if our paper gets accepted.\n\n\n***4. The conclusion is missing in the main part of the text.***\n\n Thank you for pointing out. We did not include it to avoid some repetition given space constraints, but we will add it for the camera-ready version. We will add the following ‘Conclusion and Limitations’ section to the paper. \n\n In this paper, we provide theoretical justification for using NCMs for partial identification. We show that NCMs can be used to represent SCMs with complex unknown latent distributions under mild assumptions and prove the asymptotic consistency of the max/min estimator for partial identification of causal effects in general settings with both discrete and continuous variables. Our results also provide guidelines on the practical implementation of this method and on what hyperparameters are important, as well as recommendations on values that these hyperparameters should take for the consistency of the method. These practical guidelines were validated with a small set of targeted experiments, which also showcase superior performance of the neural-causal approach as compared to a prior main contender approach from econometrics and statistics, that involves discretization and polynomial programming.\n\nAn obvious next step in the theoretical foundation of neural-causal models is providing finite sample guarantees for this method, which requires substantial further theoretical developments in the understanding of the geometry of the optimization program that defines the bounds on the causal effect of interest. We take a first step in that direction for the special case, when there are no unobserved confounders and view the general case as an exciting avenue for future work.\n\n\n\n***5. What is the performance of the method in other confounded ATE settings where the ground-truth is available, e.g., a no-assumptions bound for the ATE with hidden confounding?***\n\nThank you for asking. We do an extra experiment on the leaky mediation setting [1]. The structure equations of this causal model are \n\t\\begin{align*}\n\tT &= C + U_T, \\\\\\\\\n\tX &= T + U_X + U, \\\\\\\\\n\tY &= 2X + U +C +U_Y, \\\\\\\\\n\t\\end{align*}\nwhere $C,U,U_T,U_X,U_Y \\sim \\text{Unif}(-1,1)$ are latent variables and $T,X,Y$ are observed variables. Like the settings in our paper, we compare our algorithm with the Autobounds package. The true ATE of this model is 2. The following results are the averages of 10 experiments for each algorithm. The bounds obtained by NCM is [-4.19,4.12], while the bound obtained by Autobounds is [-10.97, 12.56]. \n\nThe bounds obtained by both algorithms seem non-informative because for this partial identification problem, the ATE can be an arbitrary real number. This is because the following causal model, with $\\alpha$ taking over all real numbers, has the same observation distribution as the ground-truth model. \n\\begin{align*}\n\tT &= C + U_T, \\\\\\\\\n\tX &= T + U_X + U, \\\\\\\\\n\tY &= \\alpha X + (3 - \\alpha)(U +C) + U_Y + (2 - \\alpha)U_X, \\\\\\\\\n\t\\end{align*}\n\tThe results of the NCM approach correctly reflect this fact. \n\n[1] Padh, Kirtan, et al. \"Stochastic causal programming for bounding treatment effects.\" Conference on Causal Learning and Reasoning. PMLR, 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": "MvvG3f0lUn", "reviewer": "Reviewer_VZrh", "summary": "This paper provides a novel perspective and solid contribution to the case where continuous and categorical variables both exist.", "questions": "How do we argue the importance of solving the problem of ``the approximation error and consistency of the optimization-based approach to partial identification via NCMs''?", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The presentation and organization are concise and clear; the contribution is solid.", "weaknesses": "The assumption is somehow strong (e.g., assumption 2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions! Below is our response. We hope our clarification can solve your problem.\n\n***1. The assumption is somehow strong (e.g., assumption 2).***\n\nThank you for your feedback. Assumption 2 is a relatively new assumption about the data generation process of categorical variables, but which again we view as a mild assumption that is basically an analog of the Lipschitz structural equation function assumption that we place on continuous variables. This assumption basically states that if one conditions on all the latent factors that are impacting a given variable and which also impact other variables (i.e. once one conditions on the latent confounders for this variable), then the probability that this categorical variable takes any given value is a Lipschitz function of this confounding latent factors. We make this intuition formal using the following formal convention. The classical definition of SCM assumes that the structural equations have the form $ V_i = f_i(\\text{Pa}(V_i),U_i) $, where $\\text{Pa}(V_i)$ is the set of parents of node $V_i$. However, if we follow this definition and $V_i$ is categorical, this means $f_i$ can only take finitely many values. If one of the inputs is a continuous variable, the only way for $f_i$ to be continuous (which is a quite mild assumption) is that $f_i$ is a constant function, which is trivial. To avoid this situation, we assume that the latent variables have two parts, the confounding part $U$ and the independent noises part $G$. The categorical variable $V_i$ is generated by the following process. First, we calculate the propensity function $f(\\text{Pa}(V_i),U_i) \\in \\Delta =\\\\{x\\in\\mathbb{R}^d:x_i \\geq 0, \\sum x_i = 1\\\\}$. Then, we generate a categorical variable according to this probability using the independent noise $G_i \\in G$. In this way, we only need to approximate the propensity in the learning process.\n\nWe also want to emphasize that the Gumbel variables in assumption 2 are chosen for convenience to generate categorical distributions in the second step mentioned above. One can replace the Gumbel variables with any random variables that can generate categorical distributions. Therefore, this assumption is basically a natural analog of the “Lipschitz structural equation” assumption, to the data generation process of categorical variables. \n\n***2. How do we argue the importance of solving the problem of “the approximation error and consistency of the optimization-based approach to partial identification via NCMs”?***\n\n\nThank you for your question. As we mentioned in our paper, identifying causal quantities from observational data is an important problem. However, in the presence of unobserved confounding, it is usually impossible to accurately identify many causal quantities. In that situation, partial identification gives a remedy to the problem. \n\nThere has been rich literature on partial identification in causal inference and the optimization-based approach has demonstrated good empirical performance [1,2,3,5].  However, in the general continuous variables setting (and the mixed setting), previous methods [1,2,3] do not have any theoretical result on the soundness of their methods. Moreover, the NCM approach is the only generic methodology for partial identification with general variables. Prior general methodologies for automated Partial Identification [5], that don’t go through the NCM method, are only available for discrete variables and, as our experiments showcase, they translate poorly to the continuous variable setting (if one invokes discretization) and don’t have natural continuous counterparts that one could analyze theoretically. Thus our paper fills this gap: provides a theoretical justification of the only existing candidate for an automated partial identification procedure for general variables. \n\n[1]Kocaoglu, Murat, et al. \"Causalgan: Learning causal implicit generative models with adversarial training.\" arXiv preprint arXiv:1709.02023 (2017).\n\n[2]Vahid Balazadeh, Vasilis Syrgkanis, and Rahul G. Krishnan. Partial identification of treatment effects with implicit generative models, October 2022\n\n[3]Kirtan Padh, Jakob Zeitler, David Watson, Matt Kusner, Ricardo Silva, and Niki Kilbertus. Stochastic causal programming for bounding treatment effects.In Conference on Causal Learning and Reasoning pages 142–176. PMLR, 2023\n\n[4] Florian Gunsilius. A path-sampling method to partially identify causal effects in instrumental variable models, June 2020\n\n[5] Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, and Ilya Shpitser. An automated approach to causal inference in discrete settings, September 2021", "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": "1dqZfWbfpN", "reviewer": "Reviewer_Mk7v", "summary": "This paper studies theoretically the partial identification capabilities of neural causal models (NCMs), that is, the extent to which this type of models can approximate the interval on which a certain causal query falls on, $\\theta(\\mathcal{M}) \\in [\\underline{F}, \\overline{F}]$. To this end, the authors develop a lot of results showing that under ideal scenarios with oracle knowledge on the exogenous distributions, NCMs can approximate any SCM if the proper architecture and regularization is used. Interestingly, the authors show that regularization is key in these settings, as otherwise the observational likelihood can be modelled arbitrarily well, while the interventional distribution do not look alike. It is worth-noting that the theory developed consider general scenarios with confounders and mixed-type data.", "questions": "I have no specific questions, but I want to make clear that a dense paper like this would require many more hours for me to fully understand it and I may have missed some important points. I will reflect this in my confidence score.", "limitations": "Limitations are **not** discussed. In the checklist, it is said to be discussed on the Conclusion section, which does not exist.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **S1.** This work addresses an intellectually interesting question of whether NCMs can properly perform causal partial identification.\n- **S2.** The theory developed looks general, sound, and it makes sense on an intuitive level (disclaimer: I have _not_ looked into the proofs).\n- **S3.** The work properly studies mixed-type data, which I have rarely seen done.\n- **S4.** The fact that NCMs _need_ a form of regularization to properly approximate the SCMs is really interesting.", "weaknesses": "- **W1.** My personal main concern is that I do not immediately see any practical implication of the theory developed here. What I mean is that, while I find it interesting, if I have understood it correctly it works under the assumption that we know the exogenous distribution of the ground-truth model, which we never know, and which we could be arbitrarily different from whatever we model (we can always change the exogenous distribution and push the transformation to the generator $f$).\n- **W2.** While trying to be general, I similarly feel that some of the assumptions can be quite restrictive in practice. E.g., global Lipschitz-continuity is quite a constraining assumption from my point of view.\n- **W3.** I know it is a dense theory paper, but the presentation leaves a lot to be desired. There is a lot of similar notation, non-standard definitions (e.g. SCMs), and a lack of intuition/examples that makes the results hard to parse. The paper is simply not accessible to a large percentage of the community.\n- **W4.** The experimental section is extremely short, and it would require of more settings, an ablation study of the different components of the theory, and a proper analysis of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! Below is our response. We hope our clarification can solve your problem. \n\n***1. The method only works under the assumption that we know the exogenous distribution of the ground-truth model.***\n\nWe thank the reviewer for their advice. However, we would like to kindly elaborate on a misunderstanding about a key criticism and we will make sure to make this point even more clearly described in the paper: Our algorithm does not need to know the ground-truth exogenous distribution of the latent factors and this is a key development of our work. We only need to assume that these unknown exogenous distributions satisfy some mild regularity assumptions (Assumption 4,5). This is a key point of partial identification. Without knowing the exact latent distribution, we search over all NCMs that induce a distribution similar to the one observed empirically (measured by a metric distance) and take the maximum and minimum of the causal quantity we are interested in subject to this metric distance constraint. \n\nIn our algorithm, we push forward uniform and Gumbel variables using neural networks to simulate exogenous distributions that satisfy Assumption 4 (and may Assumption 5, depending on which architecture to use) and see the maximum and minimum of the causal quantity of causal models whose latent distributions fall in this class (Problem (7) in the paper). A key theoretical insight of our work is that by passing these simple distributions through appropriate neural network architectures, one can represent arbitrary latent variable distributions and hence “fit” any ground truth latent distribution that satisfies the regularity assumptions. Thus arbitrary SCMs, with general unknown latent factor distributions can be represented through NCMs and when fitting to data, one does not need to know the actual distribution of the latent factors. For this reason, our theoretical results have a strong implication for practice and essentially analyze the methodology that prior work had extensively studied empirically. \n\n***2. While trying to be general, some of the assumptions can be quite restrictive in practice. E.g., global Lipschitz-continuity is quite a constraining assumption.***\n\nThanks for your feedback. We work with compactly supported distributions (Assumption 3), so a local Lipschitz function is automatically global. While certainly not fully general, the Lipshitz continuity assumption is a standard assumption in the literature on the representation theory of neural network architectures and most neural network architectures (e.g. ReLU) are in fact globally Lipschitz. Moreover, even if there is no confounding in the SCM, to learn the SCM, we need to learn the structural functions $f_i$. To avoid impossibility results, like the No-free-lunch theorem, one needs to make some structural assumptions on the function spaces that the functions $f_i$ lie in. Lipschitz function spaces are a natural choice when providing theoretical statistical consistency and representativeness theorems [3,4,5].\n\n***3. There is a lot of similar notation, non-standard definitions (e.g. SCMs), and a lack of intuition/examples that makes the results hard to parse.***\n\nThank you for your feedback. Due to space limitations, we are unable to present all the details in the main body. However, we provide some examples in the appendix.  For the definition of SCM, we follow the definition of Xia et al.[1]. The only difference with the traditional SCM literature is that we allow the latent “noise” variables to enter more than 2 observed nodes. This convention was also followed in Xia et al.[1]. The causal graph induced by an SCM in our definition is a kind of Acyclic Directed Mixed Graph obtained by latent projection [2]. We have provided one example in Appendix A to illustrate our definition.\n\n\n***4. The experimental section is extremely short, and it would require more settings and a proper analysis of the results.***\n\nThank you for your comment. As we point out in the paper, the methodology that we analyze has been proposed and analyzed experimentally in prior work. The main contribution of our paper is to provide a theoretical justification of this methodology in general environments. Please see item 1 of our response to the reviewer zYjd for details. \n\n***5. Limitations are not discussed and the conclusion is missing.***\n\nThank you for pointing out! We did not include the conclusion part due to space limitations, which can be easily addressed. We will add a ‘Conclusion and Limitations’ section in the camera-ready version, which is shown in the response of reviewer 8521 item 4.\n\n[1] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, and Elias Bareinboim. The causal-neural connection: Expressiveness, learnability, and inference, October 2022.\n\n[2] Jin Tian and Judea Pearl. On the testable implications of causal models with hidden variables, December 2002.\n\n[3] Yarotsky, Dmitry. \"Optimal approximation of continuous functions by very deep ReLU networks.\" Conference on learning theory. PMLR, 2018.\n\n[4] Yarotsky, Dmitry. \"Error bounds for approximations with deep ReLU networks.\" Neural networks 94 (2017): 103-114. \n\n[5]Wainwright, Martin J. High-dimensional statistics: A non-asymptotic viewpoint. Vol. 48. Cambridge university press, 2019.", "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:
Thanks for all the reviewers' helpful feedback. We include all the figures in our response in this PDF file.

Meta-review: This work extends neural causal models (NCMs) to the continuous and mixed-type variables and develops consistency results for partial identification. 

Overall, all reviewers were positive about the contribution of the paper and agreed that the theoretical contribuitions of the work are novel and make NCM's more general. I agree with the assessemnt and recommend acceptance.
Decision: Accept (poster)