Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
218,893 characters · 73 sections · 52 citation commands
The Honest Truth About Causal Trees: Accuracy Limits for Heterogeneous Treatment Effect Estimation Supplemental Appendix
Keywords: recursive partitioning, decision trees, causal inference, heterogeneous treatment effects
\setcounter{tocdepth}{3}
This supplement presents proofs for the results in the main paper, and several additional theoretical results. We start with a homoskedastic constant regression model in Section (ref), showing that the standard CART decision tree estimator of the (constant) conditional mean suffers from slow uniform convergence rates. In Section (ref), we then study the more challenging heterogeneous causal effect estimators discussed in the main paper: inverse probability weighting (IPW) estimator, the difference in mean (DIM) estimator, and the sum-of-square-minimization (SSE) estimator are considered in Sections (ref), (ref) and (ref), respectively. Section (ref) links the results in this supplemental appendix to those presented in the main paper.
\begingroup {0pt} {4pt}
Sets. $\mathbb{R}$ is the set of real numbers and $\mathbb{N}$ the positive integers. For $n\in\mathbb{N}$ we write $[n]=\{1,\dots ,n\}$.
Vectors and matrices. Boldface lower‑case letters (e.g. $\mathbf{x}$) denote column vectors, and boldface upper‑case letters (e.g.\ $\mathbf{A}$) denote matrices. For a vector $\mathbf{x}$, its $i$‑th component is $x_i$; for a matrix $\mathbf{A}$, its $(i,j)$‑th entry is $A_{ij}$. Denote by $\mathbf{e}_j$ the $j$-th unit vector.
Norms. For $\mathbf{x}\in\mathbb{R}^d$, define $\|\mathbf{x}\| = (\sum_{i=1}^{d} x_i^{2})^{1/2}$, and $\|\mathbf{x}\|_\infty = \max_{i\le d}|x_i|$. For a matrix $A \in \mathbb{R}^{m \times n}$, the operator norm is $\lVert A \rVert = \sup_{\lVert \mathbf{x} \rVert = 1} \lVert A\mathbf{x} \rVert$, and the max norm is $\lVert A \rVert_{\max} = \max_{1 \leq i \leq m, 1 \leq j \leq n} |A_{ij}|$. For a bounded measurable function $g$, $\|g\|_\infty = \sup_{x}|g(x)|$. For a random variable $X$ with distribution $P_X$, denote the population $L_2$ norm by $\lVert X \rVert = (\int \lVert x \rVert^2 d P_X(x))^{1/2}$; and given a random sample $\mathcal{D} = \{X_1, \cdots, X_n\}$, denote the empirical $L_2$ norm by $\lVert X \rVert_{\mathcal{D}} = (n^{-1}\sum_{i = 1}^n \lVert X_i \rVert^2)^{1/2}$.
Asymptotics. For reals sequences $a_n \ll b_n$ (or $a_n = o(b_n)$) if $\limsup_{n\to\infty} \frac{|a_n|}{|b_n|} = 0$; $|a_n| \lesssim |b_n|$ (or $a_n = O(b_n)$) if there exists some constant $C$ and $N > 0$ such that $n > N$ implies $|a_n| \leq C |b_n|$. For sequences of random variables $a_n = o_{\mathbb{P}}(b_n)$ if $\operatorname{plim}_{n \rightarrow \infty}\frac{|a_n|}{|b_n|} = 0, |a_n| \lesssim_{\mathbb{P}} |b_n|$ if $\limsup_{M \rightarrow \infty} \limsup_{n \rightarrow \infty} \mathbb{P}[|\frac{a_n}{b_n}| \geq M] = 0$.
Other. $\mathds{1}(\cdot)$ denotes the indicator function. For two random variables $X$ and $Y$, $X \protect\mathpalette{\protect\independenT}{\perp} Y$ means $X$ and $Y$ are independent. For $x \in \mathbb{R}$, $\lfloor x \rfloor$ and $\lceil x \rceil$ denote the floor and ceiling of $x$ respectively. $\mathsf{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ denotes the Gaussian distribution with mean $\boldsymbol{\mu}$ and covariance matrix $\boldsymbol{\Sigma}$. $\mathsf{Beta}(\alpha, \beta)$ denotes the Beta distribution with parameter $(\alpha, \beta)$. A stochastic process $\{B(t), 0 \leq t \leq 1\}$ is a Brownian bridge, if $B$ is a continuous Gaussian process with $\mathbb{E}[B(t)] = 0$, and $\mathbb{E}[B(t)B(s)] = \min\{t,s\} - ts$.
\endgroup
This section is self-contained, and substantially improves on the results reported in Cattaneo-Klusowski-Tian_2022_arXiv. The results presented herein are of independent interest in regression estimation settings, and they also offer a gentle introduction to the more technically involved results discussed in Section (ref).
Consider the canonical regression model where the observed data $\{(y_i,\mathbf{x}_i^T) : i = 1, 2, \dots n\}$ is a random sample satisfying
with $\mathbf{x}_i = (x_{i1}, x_{i2}, \dots, x_{ip})^T$ a vector of $p$ covariates taking values on some support set $\mathcal{X}$.
In what follows, we denote by $P_X$ the marginal distribution of $\mathbf{x}_i$.
Now we illustrate the CART estimation strategy. Given any tree $\mathsf{T}$, the CART estimator is given as follows:
We start from the no sample splitting ($\mathtt{NSS}$) case, and characterize the location of the first split.
For each variable $ j = 1, 2, \dots, p $, let $\pi_j$ be the permutation such that $ x_{\pi_{j}(i),j} $ is non-decreasing in the index $ i = 1, 2, \dots, n$. Then, minimizing Equation (ref) can be equivalently recasted as maximizing the so-called impurity gain:
where $\bar{y}_{\mathrm{t}} = n(\mathrm{t})^{-1} \sum_{\mathbf{x}_i \in \mathrm{t}} y_i \mathds{1}(\mathbf{x}_i \in \mathrm{t})$. We can show this is also equivalent to maximizing the conditional variance given the split:
We start by considering the case when the tree is depth one ($K=1$), i.e., a decision stump. Then optimization objectives are equivalent to choosing a splitting coordinate $\hat \jmath$, and a splitting index $\hat \imath$ such that
The tree output can then be written as
where $x_{\hat\jmath}$ denotes the value of the $\hat\jmath$-th component of $\mathbf{x}$.
The following theorem formally (and very precisely) characterizes the regions of the support $\mathcal{X}$ where the first CART split index $ \hat\imath $, at the root node, has non-vanishing probability of realizing. As a consequence, the theorem also characterizes the effective sample size of the resulting cells (recall the data is ordered so that $ \hat \mu = x_{\hat\imath \hat\jmath} $ and hence $ \hat\imath = \#\{\mathbf{x}_i : x_{i\hat \jmath} \leq \hat \mu \} $).
We will show that the imbalanced split issue is inherited from the decision stumps to trees of arbitrary depth.
Therefore, decision trees grown with CART methodology cannot converge faster than any polynomial-in-$n$, when uniformity over the full support of the data $\mathcal{X}$, and over possible data generating processes, is of interest.
However, for the $L_2$-risk we still have the following positive result. This is because the small cells that leads to issues in uniform consistency will have a small measure by $\mathbb{P}_X$.
For sample splitting strategy, we also present a lower bound on uniform consistency and an upper bound on $L_2$ consistency.
Compared to Theorem (ref), the lower bound on the LHS of Theorem (ref) that we characterize has one less $\sqrt{(2 + o(1)) \log \log (n)}$. Compared to Theorem (ref), the upper bound on the RHS of Theorem (ref) has $\log(np)$ replaced by $\log(n)$. These changes are due to the sample splitting strategy.
For X-adaptive trees, we leverage the decision stump result from Theorem (ref) using an iterative argument to infer inconsistency of trees of depth $K_n \gtrsim \log \log (n)$.
Since we keep the $\mathbf{x}_i$'s and refresh the $(d_i, y_i)$'s, the tree estimator has a simple form condition on $\mathbf{x}_i$'s. Hence a direct variance calculation gives us the following $L_2$-consistency result.
Using the same argument as Theorem (ref), we can show
where $C$ is a positive constant that only depends on $\sigma^2$. The direct variance calculation allows us to remove extra $\operatorname{poly-log}$ terms.
In this section, we consider the heterogeneous causal effect estimation problem from the main paper. The assumptions on the data generating process and the definitions of causal trees are the same as in the main paper. For completeness, we include them here:
And the causal trees are constructed based on the following rules:
While the estimators $\hat\tau^{\mathtt{NSS}}_{l}(\mathbf{x})$ and $\hat\tau^{\mathtt{HON}}_{l}(\mathbf{x})$, $l\in\{\mathtt{DIM},\mathtt{IPW},\mathtt{SSE}\}$ depend on the depth of the tree construction used, our the notation does not make this dependence explicit because our results only require (at least) one single split.
X-Adaptive Trees.
The transformed outcomes $y_i \frac{d_i - \xi}{\xi (1 - \xi)}, 1 \leq i \leq n,$ are i.i.d, with
and
Assumption (ref) implies $\mathbb{E}[\exp(\lambda \tilde{\varepsilon}_i)] < \infty$ for all $|\lambda| \leq 1 / \beta$ with $\beta$ only depending on $\xi$ and $\alpha$, and $\mathbb{E}[\tilde{\varepsilon}_i^2] >0$. Hence the following results are immediate corollaries from the results in Section (ref).
The $\mathtt{DIM}$ estimator can not be directly written as a regression tree with transformed outcome. However, we show that it can be approximated by an $\mathtt{IPW}$-tree. More specifically, we view the split criterion with different splitting index and coordinate as an empirical process, and show that the split criterion for $\mathtt{DIM}$ and $\mathtt{IPW}$ approximate each other.
Denote by $\pi_{\ell}$ permutation of index $[n]$ such that $x_{\pi_{\ell}(1),\ell} \leq x_{\pi_{\ell}(2),\ell} \leq \cdots \leq x_{\pi_{\ell}(n),\ell}$, $1 \leq \ell \leq p$. Consider the split criterion for the regression and ipw trees when splitting at the root note when $\#\{\mathbf{x}_{\pi_{\ell}(i)} \in t_L\} = k$: For $1 \leq \ell \leq p$, $1 \leq k \leq n$, consider
where
Notice that if we replace $\varepsilon_{\pi_{\ell}(i)}$ by $y_{\pi_{\ell}(i)}$, we would get $\hat \tau_L^\mathtt{IPW}$ (or $\hat \tau_R^\mathtt{IPW}$) instead of $\bar \tau_L^\mathtt{IPW}$ (or $\bar \tau_R^\mathtt{IPW}$). But putting $\varepsilon_{\pi_\ell(i)}$ here allows us to approximate the $\mathscr{I}^\mathtt{DIM}(\cdot, \ell)$ processes.
The optimization objective based on Definition (ref) for the regression based estimator with variance maximization is equivalent to choosing a splitting coordinate $\hat \jmath_{\text{DIM}}$, and a splitting index $\hat \imath_{\text{DIM}}$ such that
that maximizes
that is,
A technical aspect is to control for fluctuations of objects of the form $\frac{\sum_{i = 1}^k d_{\pi_{\ell}(i)} y_{\pi_{\ell}(i)}}{\sum_{i = 1}^k d_{\pi_{\ell}(i)}}$, for which we will use a truncation argument that requires $\sum_{i = 1}^k d_{\pi_{\ell}(i)} \geq r_n$ with $r_n \to \infty$. This gives the following lemma:
We also control for the truncation error:
The previous two lemmas imply that we can study $\operatorname*{arg\,max}$ of $\mathscr{I}^\mathtt{DIM}$ in terms of $\operatorname*{arg\,max}$ of $\bar \mathscr{I}^\mathtt{IPW}$. The latter is the split criterion based on CART with transformed outcome $\frac{d_i}{\xi} \varepsilon_i(1) - \frac{1 - d_i}{1 - \xi} \varepsilon_i(0)$, and results from Section (ref) can be applied.
The issue of imbalanced cells gives rise to the slow uniform convergence rate.
We generalize the above results on decision stumps to trees of arbitrary depths.
In comparison to the uniform convergence rate, for $L_2$ convergence rate we can give an upper bound as follows.
With the sample splitting strategy, we also give a lower bound on uniform convergence rate and an upper bound on $L_2$ convergence rate. The difference in rates from the rates in the previous section is due to the different sample splitting strategies.
We leverage Theorem (ref) with an iterative argument to get
A direct variance calculation gives
Using the same argument as Theorem (ref), we can show
where $C$ is a positive constant that only depends on the distribution of $(\varepsilon_i(0), \varepsilon_i(1), d_i)$. The direct variance calculation allows us to remove extra $\operatorname{poly-log}$ terms.
While the CATE estimators given the tree of the $\mathtt{SSE}$ strategy coincides with the $\mathtt{DIM}$ strategy, the tree construction methods differ. Similar to $\mathtt{DIM}$, for $\mathtt{SSE}$ we also characterize the distribution of split index via a Gaussian approximation. Here we show the split criterion with $\mathtt{SSE}$ strategy can be approximated by the split criterion from two transformed outcome regressions, one for treatment and one for control. A careful high dimensional Gaussian approximation with respect to the geometry of simple convex sets then enables us to characterize the limiting distribution of splitting indices.
For each variable $ j = 1, 2, \dots, p $, the data $ \{ x_{ij}: \mathbf{x}_i \in \mathrm{t} \} $ is relabeled so that $ x_{ij} $ is increasing in the index $ i = 1, 2, \dots, n(\mathrm{t}) $, where $ n(\mathrm{t}) = \#\{ \mathbf{x}_i \in \mathrm{t} \} $. The fit-based objective is to minimize
with respect to the index $ i $ and variable $ j $. Again, the maximizers are denoted by $ (\hat\imath_\text{SSE}, \hat\jmath_\text{SSE}) $, and the optimal split point $ \hat \tau $ that maximizes (ref) can be expressed as $ x_{\hat\imath_\text{SSE}, \hat\jmath_\text{SSE}}$.
To break down the criterion (ref), denote
Also to denote the counts compactly, $n_0 = \sum_{i = 1}^n (1 - d_i)$, $n_{L,0}(k) = \sum_{i = 1}^k (1 - d_{\pi_{\ell}(i)})$, $n_{R,0}(k) = \sum_{i = k + 1}^n (1 - d_{\pi_{\ell}(i)})$, and $n_1 = \sum_{i = 1}^n d_i$, $n_{L,1}(k) = \sum_{i = 1}^k d_{\pi_{\ell}(i)}$, $n_{R,1}(k) = \sum_{i = k + 1}^n d_{\pi_{\ell}(i)}$. Then we can show that maximizing Equation (ref) is equivalent to maximizing
We want to show the above empirical process can be approximated by
with
The latter can be approximated by the summation of two independent time-transformed O-U process (which is again a time-transformed O-U process), for fixed coordinate $\ell \in [p]$. More precisely, we present the approximation lemmas:
Notice that although the splitting criteria is different from the regression tree, once cells are given the estimator given by the fit-based tree is exactly the same as the regression tree (see Section (ref)). Hence the following results can be proved based on Theorem (ref) and the same logic as Theorem (ref) to Theorem (ref).
The fourth method proposed by Athey-Imbens_2016_PNAS is the squared T-statistic trees, where at the root node the index and coordinate to split $(\hat \imath, \hat \jmath)$ are chosen so that the squared T-statistics metric is maximized, that is,
where $\hat{\tau}_L(k,\ell)$ and $\hat{\tau}_R(k,\ell)$ are the causal tree estimators for the left and right nodes respectively based on split coordinate $\ell$ and index $k$, and $S(k,\ell)^2$ is the conditional sample variance given the split, that is,
Putting together, we see the squared T-statistics metric is a monotone transformation of the split criterion of previously studied estimators,
Hence the split is always the same as the split by the split criterion studied in Section (ref) and Section (ref).
Taking $T = c \log(n)$ in horvath1993maximum, we have
Now we expand the term $\frac{z + b_d(c\log (n))}{a(c \log(n))}$. For notational simplicity, denote
First, we present some elementary expansions, \[
\] Now we expand the terms for the numerator $b_d(c \log(n))$, \[
\] Then
Since $N_1 = 2L + O(\log \log \log(n))$, we have
Since $a(\log(n)) = \Theta(L^{1/2})$, we have
where the last line follows from convergence in distribution of $a(c \log(n)) \sup_{0 \leq t \leq c \log (n)} N(t) - b_d(c\log (n))$ to a continuous distribution and Slutsky's Theorem.
First, we introduce some notations. Recall for $\ell \in [p]$, $\pi_\ell$ denotes the permutation such that $(x_{\pi_\ell(i)}: 1 \leq i \leq n)$ is non-decreasing. Define sample mean at the left and right leave at index $k \in [n]$ based on coordinate $\ell \in [p]$ by
We can check that minimizing the sum of squares criterion Equation (ref) is equivalent to maximizing the split criterion
where
Moreover, under the constant conditional mean assumption, Assumption (ref) (1), we have that $\hat\mu_{L}(k,\ell) - \hat \mu_{R}(k, \ell) = \frac{1}{k} \sum_{i = 1}^k \varepsilon_{\pi_{\ell}(i)} - \frac{1}{n - k} \sum_{i = k+1}^n \varepsilon_{\pi_{\ell}(i)}$. Hence we can w.l.o.g. replace $y_i$ by $\varepsilon_i$ in the definition of $\hat \mu_L$ and $\hat \mu_R$, that is,
The rest of the proof is organized as follows. In Section (ref), we prove the results under $p = 1$, showing a strong approximation of the split criterion $(\mathscr{I}(k,1): k \in [n])$ by the square of a time-transformed Ornstein-Uhlenbeck (O-U) process, and studying the argmax of the split criterion through the argmax of the O-U process. In Section (ref), we generalize to allow for $p \geq 1$. We show that the split criterion over different coordinates, that is, $(\mathscr{I}(k,\ell): k \in [n])$ for different $\ell$'s, are asymptotically independent. This reduces our problem to one-dimensional calculations, and the same technique of approximation by O-U process from Section (ref) can be used.
This the case when $p = 1$. For notational simplicity, define partial sums by
By csorgo1997limit, we can define a sequence of Brownian bridges $ \{ B_n(t) : 0 \leq t \leq 1 \} $ on a suitable probability space such that
where $ \epsilon_n = o_{\mathbb{P}}\big((\log\log(n))^{-1/2}\big) $. We note that while csorgo1997limit bounds the approximation error of the maximum over the full range $ 1 \leq k < n $ as in (ref), its proof, which relies on invariance principles for partial sums of i.i.d. random variables, can be generalized to bound the approximation error over $ 1 \leq k < n^{a} $, $ n^{b} < k < n $. Thus,
We note that the standardized Brownian bridge $ \big\{ B_n(t)/\sqrt{t(1-t)} : 0 < t < 1 \big\} $ is distributionally equivalent to a time-transformed Ornstein-Uhlenbeck (O-U) process $ \big\{ U(\log(t/(1-t))) : 0 < t < 1\big\} $, where $ \big\{U(t): t \in \mathbb{R}\big\}$ is an O-U process with mean $ \mathbb{E}[U(t)] =0 $ and covariance $\mathbb{E}[U(s)U(t)] = e^{-|s-t|/2}$ csorgo1981strong, and thus
where the last equality follows from stationarity of the process $ |U(t)| $, the square of which is a Cox-Ingersoll-Ross (CIR) process jaeschke2003survey. Continuing from (ref), for any sequence $u_n$, we have
Now, since $ U(t) $ is a continuous, mean-zero Gaussian process, it induces a centered Gaussian measure on the space of all continuous functions on $\big[0,\,2\log(n-1)\big] $ equipped with the supremum norm (a separable Banach space). Thus, by the Gaussian correlation inequality latala2017royen, we have that
where the last equality follows from stationarity.
By the Darling-Erd\H{o}s Limit Theorem for the O-U process csorgo1981strong and eicker1979asymptotic, for all $ c > 0 $ and $ z \in \mathbb{R} $, we have
For a detailed proof of a generalized result on multidimensional O-U process, see Section (ref).
Let $ z^* $ maximize $ z \mapsto \exp\big(-2e^{-(z-\log(2-(b-a)))}\big) - \exp\big(-2e^{-(z-\log(2))}\big) $, and set $$ u_n = \frac{2\log\log(n) + (1/2)\log\log\log(n) + z^* - (1/2)\log(\pi)}{\sqrt{2\log\log(n)}}. $$ We combine (ref), (ref), and (ref), and employ (ref) three times with $ c = 2 $ and $ c = 2-b $, and $ c = a $, together with the fact that $ \epsilon_n = o_{\mathbb{P}}\big((\log\log(n))^{-1/2}\big) $. We have that
Now we prove for the general case of $p \geq 1$. As a sketch of the proof, we show that the split criterion over different coordinates, that is, $(\mathscr{I}(k,\ell): k \in [n])$ for different $\ell$'s, are asymptotically independent, which will imply
where in equality (*) we use asymptotic independence between $\mathscr{I}(\cdot,\ell)$ for different $\ell$'s, and the last line are one-dimensional probabilities that can be handled by O-U process approximation like in Section (ref).
To show the split criteria over different coordinates are asymptotically independent, we break down into two steps: In the first step, we show the partial sum process $n$ indices and $p$ coordinates can be approximated by another partial sum process with Gaussian increments (hence a Gaussian process), with the same covariance structure. In the second step, we show the covariance between the split criteria over any two different coordinates and any indices are vanishing. Together with Gaussianity, this implies that the split criteria over different coordinates are asymptotically independent.
For $1 \leq \ell \leq p$, denote by $H_n^\ell(\frac{k}{n})$ the scaled partial sum for the $\ell$-th coordinate evaluated at time $\frac{k}{n}$, that is,
where $\# \pi^{\ell}:[n] \rightarrow [n]$ is the inverse mapping of $\pi^{\ell}$.
We use a truncation argument for the proof. Fix $\varepsilon \in (0,1)$. Take $r_n = \exp((\log n)^{\varepsilon})$. And consider
where $\# \pi^{\ell}$ denotes the inverse mapping of $\pi^{\ell}$. Notice that we add the $\sqrt{n}$ factor for standardization. Then we can check that condition on $\mathscr{B}$, the $\sigma$-algebra generateed by the $p$ permulations $\pi^1, \cdots, \pi^p$, $\mathbf{C}_i$'s are independent, and for all $1 \leq j \leq p(n - 2 r_n)$, $1 \leq \ell \leq p$, we have
where we assume row $j$ in $\mathbf{C}_i$ corresponds to $\sqrt{n} \sqrt{\frac{n}{k(n-k)}} (\mathds{1}(\#\pi^{\ell}(i) \leq k) - \frac{k}{n})$. To use the coupling result chernozhukov2017central, we bound a few quantities: Suppose $K_1$ and $K_2$ are the universal constants given in the cited theorem,
For notational simplicity, denote $\mathtt{P} = p (n - 2 r_n)$. Take $\bar{L}_n = L_n$, then
The definition of $\mathbf{C}_i$ implies $C_{ij}$ is $\sqrt{n/r_n}$-exponential. Hence
since $r_n = \exp((\log n)^{\varepsilon})$ and $\varepsilon, p$ are fixed. Now condition on $\mathscr{B}$, let $\boldsymbol{D}_i, 1 \leq i \leq n$ to be independent mean-zero Gaussian random vectors such that
Then for each $1 \leq j \leq \mathtt{P}$, $1 \leq i \leq n$, we have $D_{ij}$ is $r_n^{-1}$-subGaussian. Hence the same argument implies
chernozhukov2017central then implies
where $\mathcal{A}^\text{re}$ is the class of all rectangles $A$ of the form
for some $- \infty \leq a_j \leq b_j \leq \infty$, $j = 1,2, \cdots, \mathtt{P}$. In particular, suppose $u_i, 1 \leq i \leq n$ are i.i.d $N(0, \mathbb{E}[\varepsilon_i^2])$ random variables, then $\boldsymbol{D}_i$ can be taken such that
The above result shows if we define
then Equation (ref) and unconditioning on $\mathscr{B}$, we get
For $1 \leq \ell \leq p$, denote by $G_n^\ell(\frac{k}{n})$ the partial sum for the $\ell$-th coordinate evaluated at time $\frac{k}{n}$, that is,
Then $\mathbf{G}_n = ((G_n^1(1/n),G_n^1(2/n),\cdots,G_n^1(n/n))^\top, \cdots, (G_n^p(1/n),G_n^p(2/n),\cdots,G_n^p(n/n))^\top)^\top$. Then $\mathbf{G}_n$ is a $np$-dimensional Gaussian random vector, and denote by $\boldsymbol{\Sigma}_n$ its covariance matrix. We want to show that $\boldsymbol{\Sigma}_n$ is close to one with covariance between different coordinates zero.
Consider two different coordinates, $\ell_1, \ell_2 \in [p]$. W.l.o.g, we can assume $\ell_1 = 1$ and $\ell_2 = 2$. Let $k,j \in [n]$. Denote by $\boldsymbol{\sigma}$ the sigma-algebra generated by $\pi_1, \cdots, \pi_p$. Then
To calculate $\sum_{i = 1}^k \sum_{i^\prime = 1}^j \mathbb{E}[u_{\pi_1(i)} u_{\pi_2(i^{\prime})}|\boldsymbol{\sigma}]$, we can first condition on $\pi_1$, and let $\mathcal{I} = \{\pi_1(i): 1 \leq i \leq k\}$. Observe that $\sum_{i = 1}^k \sum_{i^\prime = 1}^j \mathbb{E}[u_{\pi_1(i)} u_{\pi_2(i^{\prime})}|\boldsymbol{\sigma}] = |\{i^{\prime} \in [j]: \pi_1(i^{\prime}) \in \mathcal{I}\}|$. Now consider $$f(\pi) = \frac{n}{jk}|\{i \in [j]: \pi(i) \in \mathcal{I}\}|,$$ $\pi$ is a random permutation of $[n]$. Changing the order of the first $j$ values of $\pi$ does not change the value of $f(\pi)$, and $|f(\pi) - f(\pi^{s,t})| \leq \frac{n}{jk}$ for all $\pi$, $s \in \{1,\cdots,j\}$, $t \in \{j+1,\cdots,n\}$, where the permutation $\pi^{s,t}$ is obtained from $\pi$ by transposition of its $s$th and $t$th coordinates. We will show later that w.l.o.g. we can assume $j,k \leq \lceil n/2 \rceil$. Then by Lemma 2 from el2009transductive, for any $t \geq 0$,
Since $\frac{n - 1/2}{n - j}(1 - \frac{1}{2 \max(j,n-j)}) \geq 1 - \frac{1}{n}$, we can marginalize over $\pi_1$ and uncondition on $\boldsymbol{\sigma}$ to get there exists a positive constant $C$ such that for $n$ large enough, for all $j,k \in [n]$,
which implies
The reduction to $j,k \leq \lceil n/2 \rceil$ is because
Now consider a $np$-dimensional mean-zero Gaussian random vector $$\mathbf{Z}_n = ((Z_n^1(1/n),Z_n^1(2/n),\cdots,Z_n^1(n/n))^\top, \cdots, (Z_n^p(1/n),Z_n^p(2/n),\cdots,Z_n^p(n/n))^\top)^\top,$$ where for each $1 \leq \ell \leq p$, $(Z_n^\ell(1/n),Z_n^\ell(2/n),\cdots,Z_n^\ell(n/n))^\top$ has the same joint distribution as the partial sum random vector $(G_n^\ell(1/n)$,$G_n^\ell(2/n),\cdots,G_n^\ell(n/n))^\top$, and for any $\ell \neq \ell^{\prime}$ and any $j,k \in [n]$,
Denote by $\boldsymbol{\Gamma}_n$ the covariance matrix of $\mathbf{Z}_n$. We want to show $\boldsymbol{\Gamma}_n$ is close to $\boldsymbol{\Sigma}_n$. For a tight control on the rate of convergence, consider the truncated random vector,
Also by an abuse of notations, denote by $T_{r_n}(\boldsymbol{\Sigma}_n)$ and $T_{r_n}(\boldsymbol{\Gamma}_n)$ the covariance matrix of $T_{r_n}(\mathbf{G}_n)$ and $T_{r_n}(\mathbf{Z}_n)$, respectively. Then Equation (ref) implies
Additionally, we can lower bound the variance of each item of $T_{r_n}(\mathbf{Z}_n)$ by the following conditioning argument: Condition on the permutations $\pi_\ell$, $1 \leq \ell \leq p$, then
where in the third line, we have used the fact that condition on $\pi_\ell, 1 \leq \ell \leq p$, $(u_{\pi^\ell(i)})_{i \in [n]}$'s are i.i.d. $\mathsf{N}(0,1)$. By the Gaussian-to-Gaussian Comparison result chernozhuokov2022improved,
where $C$ is an absolute constant, and $T(n) = \lceil n - r_n \rceil - \lfloor r_n \rfloor$. Combining with Equation (ref) and taking $\mathbf{y} = (t_1 \mathbf{1}^\top, \cdots t_p \mathbf{1}^\top)$, $\mathbf{y} = -(t_1 \mathbf{1}^\top, \cdots t_p \mathbf{1}^\top)$ separately with $\mathbf{1}$ a vector of $T(n)$ 1's, we get
As in the previous two sections, fix $\varepsilon > 0$, and take $r_n = \exp((\log n)^{\varepsilon})$. Let $\mathcal{E} = \{\exists \ell \in [p]: \operatorname*{arg\,max}_k \mathscr{I}(k,\ell) < r_n \text{ or } \operatorname*{arg\,max}_k \mathscr{I}(k,\ell) > n - r_n\}$. Then by csorgo1997limit, and a union bound argument, we have
Hence we can effectively restrict the candidates of $\operatorname*{arg\,max}$ to $[r_n, n - r_n]$. W.l.o.g., we consider coordinate $\ell = 1$, and
Now we can using the coupling result developed previously. Using our notation, we have $\mathscr{I}(k,\ell) = (H_n^\ell(k/n))^2$. Hence
where we have used Lemma (ref) and Lemma (ref). Since we choose $r_n = \exp((\log n)^{\varepsilon})$, we have $\log(n)^{7/6} r_n^{-1/6} = o(1)$. It then follows from independence and symmetry between $Z_n^\ell$'s across different $\ell$'s that
where the third line is by similar calculation as in Section (ref). Putting together, we have
and by symmetry, we have
For simplicity, we denote $\hat{\mu}^{\mathtt{NSS}}(\mathbf{x})$ by $\hat{\mu}(\mathbf{x})$. We divide the proofs into two parts, one for uniform estimation and one for pointwise results near the boundary.
For notational simplicity, introduce the partial sum based on ordering for the $\ell$'s coordinate,
and define the optimal index for splitting based on the $\ell$'s coordinate by
Consider the event
Consider the case $\hat \imath < n^b$ on $\mathtt{Imbalance}_{\ell}$. The other case where $\hat \imath > n - n^b$ can be dealt with by symmetry. Then
where the last line is because $\imath_{\ell}$ is the index that maximize the split criterion based on the $\ell$'s coordinate, i.e.,
Fix $\epsilon > 0$. Consider the events
By csorgo1997limit $\limsup_{n \rightarrow \infty} \mathbb{P}(A^{\varepsilon}_{\ell}) = \limsup_{n \rightarrow \infty} \mathbb{P}(B^{\varepsilon}_{\ell}) = 1$. Hence for any $\epsilon > 0$,
where we have used the fact that $\mathtt{Imbalance}_{\ell}$'s are disjoint for different $\ell$'s and Theorem (ref). Equation (ref) then follows.
Consider the event
Since $\pi_{\ell}$ is the uniform permutation, we have
Together with Theorem (ref),
Then on the event $\mathtt{Off}_{\ell}$ and $x_{\ell,\imath_{\ell}} \geq n^{a-1}$, for any $\mathbf{x} \in [0,1]^p$ such that $x_{\ell} \leq n^{a-1}$, we have $x_{\ell} \leq x_{\ell,\imath_{\ell}}$, and
By similar arguments as Part 1, we can show
which is Equation (ref).
Due to the recursive splitting and Theorem (ref), the optimal split index $\hat \imath$ at the $K_n$-th split ($K_n \geq 1$) also satisfies
Hence the same argument as Part 1 in the proof of Theorem (ref) leads to the result.
This follows directly from klusowski2024large, choosing $g^{\ast} \equiv \mu$ and $g \equiv \mu$, and changing the sub-Gaussian rate to the sub-exponential rate by choosing $U \asymp \log(n)$ instead of $U \asymp \sqrt{\log(n)}$ in the truncation argument step. The last statement follows from the proof of klusowski2024large.
Throughout the proof, we abbreviate the honest tree $\hat{\mu}^{\mathtt{HON}}(\mathbf{x})$ by $\check{\mu}(\mathbf{x})$. Recall $(\hat \imath, \hat \jmath)$ denotes the optimal splitting index and coordinate for the decision stump. We use $(y_i,\mathbf{x}_i^{\top})_{i=1}^M$ to denote $\mathcal{D}_{\mathtt{HON},1}$, which we used to construct the causal tree. Denote by $(\hat \imath, \hat \jmath)$ the splitting index and coordinate at the $K_n$-th step.
Use $(\tilde{y}_i,\tilde{\mathbf{x}}_i^{\top})_{i=1}^N$ to denote $\mathcal{D}_{\mathtt{HON},2}$. By Definition (ref), $n \lesssim M,N \lesssim n$. Then
Since $\tilde{y}_i \protect\mathpalette{\protect\independenT}{\perp} \tilde{\mathbf{x}}_i$, condition on $\hat{\imath}, \hat{\jmath}$ and $\mathbf{X} = (\mathbf{x}_1, \cdots, \mathbf{x}_n)$, $\tilde{\mathbf{X}} = (\tilde{\mathbf{x}}_1, \cdots, \tilde{\mathbf{x}}_n)$, we have
where
By Marcinkiewicz–Zygmund inequality, for some positive absolute constant $C$, we have
where in the second to last line, we have used Jensen's inequality, and in the last line we have used $\tilde{\imath}$ is measurable with resepect to the $\sigma$-algebra generated by $\hat \imath, \hat \jmath, \mathbf{X}, \mathbf{X}^{\prime}$. Then by Paley–Zygmund inequality, for any $\theta \in (0,1)$,
Now we want to obtain a high probability upper bound on $\tilde \imath$ given $\imath$. Let $F$ be the cummulative distribution function of $\mathbf{x}_i$. Suppose $1 \leq k \leq N/2$. Then $F(\mathbf{x}_{(k)}) \sim \mathsf{Beta}(k, M - k + 1)$. By a Bernstein bound for Beta variables skorski_2023, we have for all $\epsilon > 0$,
where for large enough $n$,
Hence with probability at least $1 - M^{-1}$,
Condition on $\mathbf{X}$, $\mathds{1}(\tilde{\mathbf{x}}_i \leq \mathbf{x}_{(k)})$'s are i.i.d $\mathsf{Bernoulli}(F(\mathbf{x}_{(k)}))$. Hence condition on $\mathbf{X}$ and $\hat{\imath}$, with probability at least $1 - N^{-1}$,
Hence condition on the event $\hat \imath \leq M^b$, we have with probability at least $1 - 2 N^{-1}$,
where $C$ is some constant only depending on $\liminf_{n \to \infty}|D_{\mathtt{HON}, 1}|/|\mathcal{D}_{\mathtt{HON},2}|$ and $\limsup_{n \to \infty}|D_{\mathtt{HON}, 1}|/|\mathcal{D}_{\mathtt{HON},2}|$.
Due to the iterative partitioning, the conclusion for Theorem (ref) holds not only for decision stump, but also for the splitting index at arbitrary depth $K_n$, that is, for any $b \in (0,1)$, we have
Hence we have
This proves the conclusion.
For notational simplicity, we use $\mathsf{T}$ to denote the data-driven decision tree. We will follow the proof strategy from klusowski2024large condition on $\mathcal{D}_{\mathsf{T}}$. Denote by $\mathscr{G}_0$ the class of constant functions. Decompose $\lVert \hat{\mu}(\mathsf{T}) - \mu \rVert^2 = E_1 + E_2$, where
and
Denote the partition for $\mathsf{T}$ by $\mathcal{P}$. Since $\mathcal{P}$ is independent to $\mathcal{D}_{\mu}$, the bound (E.27) from klusowski2024large does not apply automatically. Instead, we consider $\mathscr{G}_0$ as the reference class. Given the partitions of $\mathsf{T}$, the values of leaf nodes are obtained by least-square projection using $\mathcal{D}_{\mu}$. This immediately implies
for any constant function $g \in \mathscr{G}_0$. Hence for all $g \in \mathscr{G}_0$,
For the term $E_1$, we first assume $|y_i| \leq U$. Observe that condition on $\mathcal{D}_{\mathsf{T}}$, $\hat{\mu}(\mathsf{T})$ is still a member of the class $\mathscr{G}_{n_{\mathsf{T}}}[\mathcal{P}]$, which is the collection of all piecewise constant functions (bounded by $U$) on the partition $\mathcal{P}$. Since for any $\varepsilon \in (0,1)$,
we can still use Gyorfi-etal_2002_book and the same argument from Equation (B.30) to (B.33) in klusowski2024large to get
The result then follows choosing $\alpha \asymp \frac{U^4 2^K \log(n)}{n}$ and $\beta \asymp \frac{U^2}{n}$, and truncation argument over the sub-exponential $\varepsilon_i$'s.
In this section, we prove Theorem (ref). First, we define some notation related to the tree construction which will be used in the proofs. Let $\tilde n_k$ be the number of observations in the node containing $x = 0$ at depth $k$, $\tilde\imath_{k} $ be the CART split index of this node, and $\tilde \jmath_{k}$ be the CART split coordinate of this node, with $\tilde n_0 = n$ and $\tilde\imath_0 = \hat\imath$ (recall that $ \hat\imath $ is the split index for the decision stump (ref)). Then, the left-most cell at the $k$-th level can be expressed as $ \mathbf{t} \cap [0, x_{ \pi_{\tilde{\jmath},\tilde{\jmath}}(\tilde\imath_{k-1})}] $ and $ \tilde n_k = \tilde \imath_{k-1}$.
Next, we use Lemma (ref) to finish the proof of Theorem (ref). The main idea is to establish that the terminal nodes in a shallow tree will be small with constant probability.
For simplicity, denote $\hat{\mu}^{\mathtt{X}}(\mathbf{x})$ by $\tilde \mu(T_K)(\mathbf{x})$, and $N = n/(K+1)$ denotes the sample size for each folds in the $\mathtt{X}$ sample splitting scheme.
Let $\mathsf{t}_1, \mathsf{t}_2, \cdots, \mathsf{t}_{2^K}$ denote the $2^K$ leaf nodes in the decision tree, (if a node cannot be further refined, we duplicate the split indices and values at the next level). And let $N_1, N_2, \cdots, N_{2^K}$ and $m_1, m_2, \cdots, m_{2^K}$ denote the number of observations and the Lebesgue measure of the $2^K$ leaf nodes, respectively. Note that $\Vec{N} = (N_1, \cdots, N_{2^{K}})$ are independent of the $\tilde y_i $ data by the honest condition and the $x_i $ data per Assumption (ref).
Claim: Condition on $\Vec{N}$, $m_k \sim \mathsf{Beta}(N_k, N - N_k + 1)$
Thus, the IMSE can be bounded as follows:
Proof of Claim: We show by induction. Base Case: K = 1. For decision stumps, for some coordinate $j \in [p]$, we have $m_1 = x_{(N_1)}$, and $m_2 = x_{(N_1 + N_2)} - x_{(N_1)} = 1 - x_{(N_1)}$. By Assumption (ref), the order statistics $x_{j,(i)}$ is independent to $\Vec{N}$. Hence $m_k \sim \mathsf{Beta}(N_k, N - N_k + 1)$, $k = 1,2$.
Induction Step: $K \geq 2$. Let $\mathsf{t}_l^{\text{prev}}$ be a $(K - 1)$-th level node, we annonate all relevant depth $K-1$ information with superscript $\text{prev}$. We already know condition on $N_1^{\text{prev}}, \cdots, N_{2^{K-1}}^{\text{prev}}$, $m_l^{\text{prev}} \sim \mathsf{Beta}(N_l^{\text{prev}}, N - N_l^{\text{prev}} + 1)$. Suppose $\mathsf{t}_l^{\text{prev}}$ is divided into $\mathsf{t}_{2l}, \mathsf{t}_{2l+1}$ with Lebesgue measure and number of observations given by $m_{2l}, m_{2l+1}$ and $N_{2l}$, $N_{2l+1}$, respectively, and the split is based on coordinate $j \in [p]$. By Assumption (ref), condition on $\mathbf{x}_i \in \mathsf{t}_l^{\text{prev}}$, $\mathbf{x}_i \sim \mathsf{Uniform}(\mathsf{t}_l^{\text{prev}})$. Hence condition on $N_l^{\text{prev}}$, $N_{2l}$ and $m_l^{\text{prev}}$, we have $m_{2l}/m_{l}^{\text{prev}} \sim \mathsf{Beta}(N_l^{\text{prev}}, N - N_l^{\text{prev}} + 1)$. Hence condition on $\vec{N} = (N_1, \cdots, N_{2^K})$, we have $m_k \sim \mathsf{Beta}(N_k, N - N_k + 1)$, $1 \leq k \leq 2^K$. Induction then concludes the proof.
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
This is an immediate corollary from Theorem (ref).
Since the number of coordinate $p$ is fixed, we can use a union bound over the approximation error for the $p$ coordinates. Hence w.lo.g. we can assume $p = 1$ and drop the second index on the coordinate $\ell$ from $\mathscr{I}^{\mathtt{DIM}}(k,\ell)$ and $\bar \mathscr{I}^{\mathtt{IPW}}(k,\ell)$ everywhere. And throughout, we assume the data is already sorted so that
Expand the square, we have for any $k = 1,2,\cdots,n$,
We focus on the case where $1 \leq k \leq \frac{n}{2}$, the other case where $\frac{n}{2} < k \leq n$ follow from symmetry. Consider the term $R_2(k)$. First, consider the term corresponding to $i$ from $1$ to $k$. The other term corresponding to $i$ from $k + 1$ to $n$ can be handled similarly. Breaking down $y_i(1) = \mu_1(x_i) + \varepsilon_i(1)$ and $y_i(0) = \mu_0(x_i) + \varepsilon_i(0)$, we have
Notice that Assumption (ref) (ii) implies that the last term is zero. Since $x_i \protect\mathpalette{\protect\independenT}{\perp} d_i$, even though the data is ordered according to $x_i$, $\{d_i/\xi - 1: 1 \leq i \leq n\}$ are i.i.d mean-zero with bounded second moment. By Theorem A.4.1 in csorgo1997limit,
Take $b_i = \sum_{1 \leq \ell \leq i} d_\ell$. By Equation (8) from shorack1976inequalities, for any $\lambda > 0$,
The assumption that $\liminf_{n \rightarrow \infty} \rho_n \log \log (n) = \infty$ implies $\liminf_{n \rightarrow \infty} r_n = \infty$. Hence
Hence uncondition on $(d_i)_{1 \leq i \leq n}$, and we have
Hence
By similar arguments, we can show the same bound holds for other terms in the first two lines of Equation (ref). Hence
Under the assumption that $\mu_0 \equiv c_0$ and $\mu_1 \equiv c_1$, we have
By Equation (ref) and Theorem A.4.1 in csorgo1997limit for the terms $k^{-1}\sum_{i = 1}^k \xi^{-1} d_i \varepsilon_i(1)$, $k^{-1} \sum_{i = 1}^k (1 - \xi)^{-1} (1 - d_i) \varepsilon_i(0)$ and the counterparts for $t_R$, we have
Putting together the parts for $R_1$ and $R_2$, we have
Since the number of coordinates $p$ is fixed, we can use a union bound over the approximation error for the $p$ coordinates. Hence w.lo.g. we can assume $p = 1$ and drop the second index on the coordinate $\ell$ from $\mathscr{I}^{\mathtt{DIM}}(k,\ell)$ and $\bar \mathscr{I}^{\mathtt{IPW}}(k,\ell)$ everywhere. And throughout, we assume the data is already sorted so that
For $1 \leq k \leq s_n$ and $n - s_n \leq k \leq n$, Equations (ref) and (ref) still hold. W.l.o.g assume $1 \leq k \leq s_n$. First, we upper bound the IPW terms. Definition of $s_n$ and Equation (A.4.3) in csorgo1997limit imply
with $u_n = \sqrt{\rho_n \log \log(n)}$. Also Equation (A.4.2) in csorgo1997limit imply
where $v_n = \sqrt{\frac{s_n}{n - s_n} \log \log (n)}$. Again Equation (A.4.3) from csorgo1997limit imply that
Take $b_i = \sum_{1 \leq \ell \leq i} d_\ell$. By Equation (8) from shorack1976inequalities, for any $\lambda > 0$,
Hence uncondition on $(d_i)_{1 \leq i \leq n}$, and we have
It follows that
Putting together the above equation with Equation (ref) and using a similar argument for the control group,
Apply Equation (A.4.2) in csorgo1997limit for the partial sum with at least $n - s_n$ terms and using $\max_{1 \leq k \leq s_n}|\frac{1}{n - k}\sum_{i = k+1}^n (d_i - \xi)| = o_\mathbb{P}(1)$, we have
The same bound hold for $\max_{1 \leq k \leq s_n} \sqrt{k} \cdot |\frac{\sum_{i = k+1}^n (1 - d_i)\varepsilon_i(1)}{\sum_{i = k+1}^n (1 - d_i)}|$ by a similar argument. Putting together Equations (ref),(ref), (ref), (ref), we have
From the decomposition in Equation (ref) and the symmetry for $k \in [1,s_n]$ and $k \in [n - s_n,n]$, the conclusion follows.
We break down the proofs into two steps.
Let $0 < a < b < 1$. Let $\rho_n$ be a sequence of real numbers taking values in $(0,1)$ to be determined, and take $s_n = \exp((\log n)^{\rho_n})$. Then for large enough $n$, we have $s_n \leq n^a \leq n^b \leq n - s_n$. Consider the event $A_n := \{\exists \ell \in [p]: \max_{k \in [n]} \mathscr{I}^\mathtt{DIM}(k,\ell) > \max_{k \notin [s_n,n - s_n]} \mathscr{I}^\mathtt{DIM}(k,\ell)\}$. By Equation (A.4.18) from csorgo1997limit,
Then controlling the difference between $\bar\mathscr{I}^{\mathtt{IPW}}(k,\ell)$ and $\mathscr{I}^{\mathtt{DIM}}(k,\ell)$ by Lemma (ref),
By Lemma (ref) with the choice $r_n = s_n$,
Equation (A.4.20) in csorgo1997limit imply that $(2 \log \log (n))^{-1/2} \max_{1 \leq k \leq n} \sqrt{\bar\mathscr{I}^{\mathtt{IPW}}(k,\ell)} = 1 +o_{\mathbb{P}}(1)$ and $(2 \log \log (n))^{-1/2}\max_{1 \leq k \leq s_n, n - s_n \leq k \leq n} \sqrt{\bar\mathscr{I}^{\mathtt{IPW}}(k,\ell)} = \rho_n(1 + o_\mathbb{P}(1))$. Hence
Choose $\log \log \log \log(n)/\log \log(n) \ll \rho_n \ll 1$, then by Equation (ref) and (ref),
Hence
which by a union bound implies
Observe that on the event $A_n^c$, the argmax for $\mathscr{I}^{\mathtt{DIM}}$ should be inside $[s_n, n - s_n]$. Hence
Now we focus on the first term. By symmetry in the $p$ coordinates,
Then using the fact that $\bar \mathscr{I}^\mathtt{IPW}(k,\ell)$ approximates $\mathscr{I}^\mathtt{DIM}(k,\ell)$ from Lemma (ref), we have
where $v_n = O_\mathbb{P}(\log \log (n) s_n^{-1/2})$.
Observe that the choice $s_n = \exp(\log(n)^{\rho_n})$ for $\log \log \log \log(n)/\log \log(n) \ll \rho_n \ll 1$ implies $\upsilon_n = o_{\mathbb{P}}((\log \log (n))^{-1/2})$. Let $\epsilon > 0$. Then
Choosing $z_n(u) = \frac{2 \log \log (n) + 1/2 \log \log \log (n) + u - 1/2 \log(\pi)}{\sqrt{2 \log \log (n)}}$, and from the proof of Theorem (ref), we have
Now let $\epsilon \downarrow 0$, and then all previous steps together implies
The proofs follow the essentially same logic as the proof for Theorem (ref), with some tricks for the random numerator in $\frac{\sum_{1 \leq i \leq k} d_i \varepsilon_i(1)}{\sum_{1 \leq i \leq k} d_i}$.
Denote the optimal index for splitting based on the $\ell$'s coordinate by
For notational simplicity, denote
and consider the event
Since we assume $\mu_0 \equiv c_0$ and $\mu_1 \equiv c_1$ with $c_1 - c_0 = \tau$, we have on $\mathtt{Imblce}_{\ell}^\mathtt{DIM} \cap \{\hat{\iota}_{\ell}^\mathtt{DIM} \leq n/2\}$,
Take $\bar\tau^{\mathtt{DIM}} = \frac{\hat{\imath}_{\text{DIM},\ell}}{n} \bar\tau^\mathtt{DIM}_L + \frac{n - \hat{\imath}_{\text{DIM},\ell}}{n} \bar\tau^\mathtt{DIM}_R$. Then
By Lemma (ref) and Lemma (ref) with $r_n = s_n = \exp((\log n)^{\rho_n})$ for $\log \log \log \log (n)/\log \log(n) \ll \rho_n \ll 1$,
By Theorem A.4.1 in csorgo1997limit, $\max_{1 \leq k \leq n} \bar \mathscr{I}^\mathtt{IPW}(k) = 2 \log \log (n) (1 + o_\mathbb{P}(1))$. Moreover,
For simplicity in showing the upper bound for $\hat{\imath}_{\text{DIM},\ell} \bar{\tau}_L^{\mathtt{DIM}}(\ell)^2 \mathds{1}(\hat{\imath}_{\text{DIM},\ell} > n/2) $, we assume $\pi$ is the identity permulation. Take $b_i = \sum_{1 \leq j \leq i} d_j$. By Equation (8) from shorack1976inequalities, for any $\lambda > 0$,
And since $d_i$'s are i.i.d with $\mathbb{E}[d_i] = \xi > 0$, we have
Hence uncondition on $(d_i)_{1 \leq i \leq n}$, and we have
By a similar term for control, and a symmetric argument for the right node,
Fix $\epsilon > 0$. Consider the events
The above arguments show that $\liminf_{n \rightarrow \infty} \mathbb{P}(A_{\ell}^{\epsilon}) = \liminf_{n \rightarrow \infty} \mathbb{P}(B_{\ell}^{\epsilon}) = 1$. From Theorem (ref), $$\mathbb{P}(\mathtt{Imblce}_{\ell}^\mathtt{DIM}) \geq \frac{b}{pe}.$$ It then follows from a union bound argument that
Fix $\mathbf{z} \in \mathcal{X}$ such that $z_{\ell} \leq n^{a - 1}$. Since the order statistics $x_{(n^a),\ell} = n^{a - 1}(1 + o_\mathbb{P}(1))$, on the event $n^a \leq \hat{\imath}_{\text{DIM},\ell} \leq n^b$, if $z_{\ell} \leq (1 + o_\mathbb{P}(1))n^{a-1}$, then $z_{\ell} \leq x_{(n^a)} \leq x_{(\hat{\imath}_{\text{DIM},\ell}),\ell}$, and on the event $\mathtt{Imblce}_{\ell}^\mathtt{DIM}$,
where the second to last line is due to a similar argument as in the proof of part 1. By a symmetry argument for the event $\{n - n^b \leq \hat{\imath}_{\text{DIM},\ell} \leq n - n^a\}$, we have
where $\mathcal{X}_n = \{\mathbf{x} \in [0,1]^p: x_j = o(1) n^{a-1} \text{ or } 1 - x_j = o(1) n^{a-1} \text{ for some } j \in [p]\}$, and $\sigma^2 = \mathbb{V}[\frac{d_i y_i(1)}{\xi} + \frac{(1 - d_i) y_i(0)}{1 - \xi}]$.
Due to the recursive splitting and Theorem (ref), the optimal split index $\hat \imath_\mathtt{DIM}$ at the $k$-th split ($k \geq 1$) also satisfies
Hence the same argument as Part 1 in the proof of Theorem (ref) leads to the result.
For notational simplicity, denote $\hat\tau^{\mathtt{NSS}}_{\mathtt{DIM}}$ by $\hat{\tau}$, the data-driven partition $\mathcal{D}_{\mathsf{T}}$ by $\mathcal{P}$.
Observe that the leaf nodes value coincide with a least square projection given $\mathcal{P}$: For $\mathsf{t} \in \mathcal{P}$, we have $\hat{\tau}(\mathsf{t}) = \hat{b}_{\mathsf{t}}$, where
Consider the outcome prediction model based on partition $\mathcal{P}$:
where
First, we show that for $L_2$-consistency of treatment effect estimation, it is enough to look at the $L_2$ loss for outcome prediction. Denote by $P_{X,d}$ the joint distribution of $(\mathbf{x}_i, d_i)$. Since we assumed $\mathbf{x}_i$ and $d_i$ are independent, we have $P_{X,d} = P_X \times P_d$, where $P_X$ and $P_d$ are the marginal distributions of $X$ and $d$. Given Assumption (ref), the target outcome prediction model is
Hence
It follows that
Now, we bound the least square error $\mathbb{E}[\lVert \hat{g} - g^{\ast}\rVert^2]$ following the strategy for klusowski2024large. First, assume $|y_i(t)| \leq U$, $i = 1,2, \cdots, n$, $t = 0,1$, for some $U \geq 0$. Decompose by
where
The least square representation (ref) implies that
which implies
We control $E_1$ using uniform law of large number arguments. Notice that $\hat{g}$ is one member of the class $\mathscr{G}_{n} = \{A(\mathbf{x}) + d \; B(\mathbf{x}): A, B \in \mathscr{H}_n\}$, where $\mathscr{H}_n$ is the class of piecewise constant functions (bounded by $U$) on partitions $\mathbb{P} \in \Pi_n$. Here
is the family of all achievable partitions $\mathcal{P}$ by growing a depth $K$ binary tree on $n$ points by iteratively splitting in $\mathbf{x}$-space based on any criterion. By klusowski2024large,
A union bound then gives
where $P_{X^n}$ is the empirical measure based on $X^n = (X_1, \cdots, X_n)$, $X_i \in \mathbb{R}^p$ for all $i$. Since $\hat{g} \in \mathscr{G}_n$, we can then use Gyorfi-etal_2002_book to get
Choosing $\alpha \propto \frac{U^4 2^K \log(np)}{n}$, and $\beta \propto \frac{U^2}{n}$, then we have
where $C$ is a positive universal constant.
Now we relax the condition that $|y_i(t)| \leq U$. Take $A = \{|y_i(t)| \leq U, \forall i = 1, \cdots, n, t = 0,1\}$. Then
A union bound gives
Using Cauchy-Schwarz inequality,
Choosing $U = \max\{\mu_0, \mu_1\} + 4 \log(n)$, we have
for some absolute constant $C$. Putting it back to Equation (ref), we get the desired conclusion.
For the high probability bound, the same analysis as Equation (ref) in almost sure sense gives
almost surely. Using sub-exponentianity of $\varepsilon_i(t)$,
with probability at least $n^{-C_2}$, where $C_1$ and $C_2$ are some positive absolute constants. Sub-exponentianity of $\varepsilon_i(t)$, $1 \leq i \leq n$, $t = 0,1$, implies that $\mathbb{P}(A^c) = n^{-C_3}$ if we choose $U = C_4 \log(n)$, where $C_3$ and $C_4$ are positive constants only depending on the distribution of $(\varepsilon_i(0), \varepsilon_i(1))$. Combining with the previous two inequalities, we get the second conclusion.
Recall $(\hat \imath, \hat \jmath)$ denotes the optimal splitting index and coordinate for the decision stump. Denote $\hat\tau^{\mathtt{HON}}_{\mathtt{DIM}}(\mathbf{x})$ by $\check{\tau}(\mathbf{x})$ for simplicity. We use $(y_i,\mathbf{x}_i^{\top})_{i=1}^M$ to denote $\mathcal{D}_{\mathtt{HON},1}$, which we used to construct the causal tree. Denote by $(\hat \imath, \hat \jmath)$ the splitting index and coordinate at the $K_n$-th step, based on $\mathcal{D}_{\mathtt{HON},1}$.
Use $(\tilde{y}_i,\tilde{\mathbf{x}}_i^{\top})_{i=1}^N$ to denote $\mathcal{D}_{\mathtt{HON},2}$. Then
Since $(\tilde{\varepsilon}_i(0), \tilde{\varepsilon}_i(1)) \protect\mathpalette{\protect\independenT}{\perp} \tilde{\mathbf{x}}_i$, condition on $\hat{\imath}, \hat{\jmath}$ and $\mathbf{X} = (\mathbf{x}_1, \cdots, \mathbf{x}_n)$, $\tilde{\mathbf{X}} = (\tilde{\mathbf{x}}_1, \cdots, \tilde{\mathbf{x}}_n)$, we have
where
Call
\paragraph*{High probability lower bound on $Z$.} Denote $n_1 = \sum_{i=1}^{\tilde{\iota}} d_i, n_0 = \sum_{i=1}^{\tilde{\iota}} (1-d_i), n_0 + n_1 = \tilde{\iota}.$ And consider the weights $w_i = \frac{d_i}{n_1} - \frac{1-d_i}{n_0}$, so that $Z = |\sum_{i=1}^{\tilde{\iota}} w_i \varepsilon_i|.$ By Marcinkiewicz–Zygmund inequality and a Jensen's inequality on the square root function, for some absolute constant $c_{\mathrm{MZ}}$,
Moreover, Assumption (ref) implies that $$ \mathbb{E}[Z^{2} \mid \bm D, \tilde{\iota}] = \frac{\sum_{i=1}^{\tilde{\iota}} d_i \mathbb{E}[\varepsilon_i(1)^{2}]}{n_1^{2}} + \frac{\sum_{i=1}^{\tilde{\iota}} (1-d_i) \mathbb{E}[\varepsilon_i(0)^{2}]}{n_0^{2}} \ge \left(\frac{1}{n_1} + \frac{1}{n_0}\right) \min\{\mathbb{V}[\varepsilon_i(1)], \mathbb{V}[\varepsilon_i(0)]\}. $$ The Paley-Zygmund inequality implies for $\theta \in (0,1)$,
Condition on $\tilde{\iota}$, $n_0 \sim \mathsf{Bernoulli}(\tilde{\iota}, \xi)$. Hence
We claim that whenever $s_n \leq \hat{\iota} \leq n - s_n$,
It then follows from Equation (ref) that whenever $s_n \leq \hat{\iota} \leq M - s_n$,
Choose $\theta = 1/2$, and take
Then by Theorem (ref), we have
We can show via the same argument as Theorem (ref) that $\liminf_{n \to \infty}\mathbb{P}(\tilde{\iota} \leq n^b/2|\hat{\iota} \leq n^b) = 1$. Hence
\paragraph*{Proof of Equation (ref).} Let $F$ be the cummulative distribution function of $\mathbf{x}_i$. Suppose $1 \leq k \leq n/2$. Then $F(\mathbf{x}_{(k)}) \sim \mathsf{Beta}(k, M - k + 1)$. By a Bernstein bound for Beta variables skorski_2023, we have for all $\epsilon > 0$,
where for large enough $n$,
Hence with probability at least $1 - s_n^{-1}$,
Condition on $\mathbf{X} = (\mathbf{x}_1, \cdots, \mathbf{x}_n)$, $\mathds{1}(\tilde{\mathbf{x}}_i \leq \mathbf{x}_{(k)})$'s are i.i.d $\mathsf{Bernoulli}(F(\mathbf{x}_{(k)}))$. Hence condition on $\mathbf{X}$ and $\hat{\iota}$, with probability at least $1 - s_n^{-1}$,
It follows that on $s_n \leq \hat{\iota} \leq M - s_n$, using boundedness of $(1 - \frac{1}{\tilde{\iota}})\mathds{1}(\tilde{\iota} > 0)$,
For simplicity, denote $\hat\tau^{\mathtt{HON}}_{\mathtt{DIM}}$ by $\hat{\tau}$. Since given the partition $\mathcal{P}$ chosen by $\mathcal{D}_{\mathsf{T}}$, Equation (ref) is still satisfied. We can use the same argument in the proof of Theorem (ref) condition on $\mathcal{D}_{\mathsf{T}}$ to get
where $C$ is a positive constant that only depends on $\xi$, $\mu$ and the distribution of $\varepsilon_i(0), \varepsilon_i(1)$. In particular, the expectation is taken with respect to $\mathcal{D}_{\tau}$ with effective sample size $n_{\tau}$.
Since condition on $\mathcal{D}_{\mathsf{T}}$, the partition $\mathcal{P}$ is fixed, we can use the same argument as in Theorem (ref) to show that $\hat{g}$ lies in a class $\mathscr{H}_{n_{\mathsf{T}}}[\mathcal{P}]$ with covering number,
when we assume $y_i(0)$ and $y_i(1)$ are bounded by $U$. In comparison, in the proof of Theorem (ref), we show $\hat{g}$ lies in $\mathscr{H}_{n_{\mathsf{T}}}$ with covering number
This improvement of covering number due to honesty means we can replace a $ \log(n_{\tau} p)$-penalty in the result of Theorem (ref) by $\log(n_{\tau})$. Now uncondition over $\mathcal{D}_{\mathsf{T}}$ and using the fact that $\rho^{-1} \leq n_{\tau}/n_{\mathsf{T}} \leq \rho$, we get the conclusion.
The conclusion follows from Theorem (ref) and the same proof for Theorem (ref).
For simplicity, denote $\hat{\tau}^{\mathcal{X}}_{\mathtt{DIM}}(\mathbf{x}; K)$ by $\tilde \tau(T_K)$, and $N = n/(K+1)$ denotes the sample size for each folds in the $\mathtt{X}$ sample splitting scheme.
Let $\mathsf{t}_1, \mathsf{t}_2, \cdots, \mathsf{t}_{2^K}$ denote the $2^K$ leaf nodes in the decision tree, (if a node cannot be further refined, we duplicate the split indices and values at the next level). And let $N_1, N_2, \cdots, N_{2^K}$ and $m_1, m_2, \cdots, m_{2^K}$ denote the number of observations and the Lebesgue measure of the $2^K$ leaf nodes, respectively. Note that $\Vec{N} = (N_1, \cdots, N_{2^{K}})$ are independent of the $\tilde y_i $ data by the honest condition and the $x_i $ data per Assumption (ref). As in the proof of Theorem (ref), we can show condition on $\Vec{N}$, $m_k \sim \mathsf{Beta}(N_k, N - N_k + 1)$
Thus, the IMSE can be bounded as follows: Since condition on $\Vec{N}$, $m_k$'s are independent to the refreshed samples $\tilde{d_i}, \tilde{\varepsilon}_i(0)$, $\tilde{\varepsilon}_i(1)$'s, we have
Notice that condition on $\Vec{N}$, $\sum_{\mathbf{x}_i \in \mathsf{t}_k} d_i \sim \mathsf{Bin}(N_k, \xi)$ and $\sum_{\mathbf{x}_i \in \mathsf{t}_k} 1 - d_i \sim \mathsf{Bin}(N_k, 1 - \xi)$. Using the fact that for a binomial random variable $W \sim \mathsf{Bin}(n,p)$, we have
where $C$ is an absolute constant, and $C_p$ is some constant that only depends on $p$. It follows that
Assume w.l.o.g. $k \leq n/2$, since the case of $k > n/2$ can be dealt with by symmetry. From the proof of Lemma (ref),
Moreover, the proof of the term $R_1$ in Lemma (ref) implies
Now we consider the randomness induced by $n_0, n_{L,0}, n_{R,0}$. By Theorem A.4.1 in csorgo1997limit,
which implies
Putting together, triangle inequality implies
The proof of Lemma (ref) implies that
where $\alpha_n = \rho_n \log \log n + \frac{s_n}{n - s_n} \log \log n$, and
Hence it also follows that
When $1 \leq k \leq s_n$, we have $\frac{n_{L,0}(k) n_{R,0}(k)}{n_0} \leq n_{L,0}(k) \leq k$. The conclusion then follows.
The proof is similar to the proof of Theorem (ref), except that in Theorem (ref), we approximate the split criterion by a time-transformed O-U process, while here we approximate the split criterion by the summation of two independent time transformed O-U processes. We divide the proofs into two steps.
Let $0 < a < b < 1$. Let $\rho_n$ be a sequence of real numbers taking values in $(0,1)$ to be determined, and take $s_n = \exp((\log n)^{\rho_n})$. Then for large enough $n$, we have $s_n \leq n^a \leq n^b \leq n - s_n$. Consider the event
Equation (A.4.18) and (A.4.20) imply that for each $\ell \in [p]$,
Hence
Approximations results from Lemma (ref) (taking $r_n = s_n$) and Lemma (ref), using the same argument as step 1 in the proof of Theorem (ref), with $\log \log \log \log(n)/\log \log(n) \ll \rho_n \ll 1$, then implies
Using a union bound, we get $\mathbb{P}(A_n) \rightarrow 0$ as $n \rightarrow \infty$. Observe that on the event $A_n^c$, the argmax for $\mathscr{I}^{\text{SSE}}$ should be inside $[s_n, n - s_n]$. Hence
Now we focus on the first term. By symmetry in the $p$ coordinates,
Then using the fact that $\mathscr{I}^\text{prox}(k,\ell)$ approximates $\mathscr{I}^\text{SSE}(k,\ell)$ from Lemma (ref), we have
where $v_n = O_\mathbb{P}(\log \log (n) s_n^{-1/2})$.
Recall that
and we will show that high dimensional random vector $\Xi$ from concatenating $(\sqrt{(1 - \xi) \frac{k (n - k)}{n}}(\bar \mu_{L,0}(k,\ell) - \bar \mu_{R,0}(k,\ell)): k \in [n], \ell \in [p])$ and $(\sqrt{(1 - \xi) \frac{k (n - k)}{n}}(\bar \mu_{L,1}(k,\ell) - \bar \mu_{R,1}(k,\ell)): k \in [n], \ell \in [p])$ can be approximated by a Gaussian random vector with the same covariance structure. The proof will still be based on writing $\Xi$ as $\frac{1}{\sqrt{n}}\sum_{i = 1}^n \mathbf{C}_i$ where
where $\# \pi^{\ell}$ denotes the inverse mapping of $\pi^{\ell}$, as in the proof of Theorem (ref).
Notice that the random vectors are $2 n p$ dimensional. For notational simplicity, in what follows, denote by $\mathbf{e}_{t,k,\ell}$ the indicator of the position corresponding to $\sqrt{(1 - \xi) \frac{k (n - k)}{n}}(\bar \mu_{L,t}(k,\ell) - \bar \mu_{R,t}(k,\ell))$, $t = 0,1$, $k \in [n]$, $\ell \in [p]$.
However, the format of Equation (ref) induces a different geometry when approximating probabilities in Equation (ref). Instead of high dimensional CLT for hyper-rectangles, we consider the class of simple convex sets chernozhukov2017central.
Let $\mathcal{J}$ be a subset of $[n] \times [p]$. Consider the class of closed convex sets $\mathcal{A}$ containing sets of the form
where $B_2(r)$ denotes the Euclidean ball centered at $\mathbf{0}$ with radius $r$ in $\mathbb{R}^2$. That is, the class $\mathcal{A}$ contains intersections of cylinders $\{\mathbf{u} \in \mathbb{R}^{2np}: \lVert {(\mathbf{e}_{j_1}^\top \mathbf{u}, \mathbf{e}_{j_2}^\top \mathbf{u})} \rVert_2 \leq s\}$. Notice that for $z \in (0, n]$, the event in Equation (ref) (inside $\sup z$) can be characterized as the high dimensional vector $\Xi$ lies in a set in $\mathcal{A}$.
For each $A \in \mathcal{A}$, we consider its approximation by simple convex sets. For each $B_2(r)$, denote by $B_2^{\text{in},n}(r)$ and $B_2^{\text{out},n}(r)$ its inscribed and circumscribed regular $n^2$-gon. Take $m = n^2 |J|$. Then for each $A \in \mathcal{A}$ of the form (ref), take
and
Then $A^m \subseteq A \subseteq A^{m,\epsilon}$. Moreover, denote by $\mathcal{V}(A^m)$ the set consisting of $m$ unit vectors that are outward normal to the facets of $A^m$. Then $A^m$ can be alternatively characterized by
Then we can analogously characterize $A^{m,\epsilon}$ by
where $\epsilon_{\mathbf{v}} \leq n^{-1}$ for large enough $n$. This shows our class $\mathcal{A}$ is a subclass of $\mathcal{A}^\text{si}(1, 3)$ (see chernozhukov2017central). Now we check its conditions (M.1'), (M.2') and (E.1'). Let $\mathbf{v} \in \mathcal{V}(A^m)$. The definition of $A^m$ implies $\mathbf{v} = v_{0,k,\ell} \mathbf{e}_{0,k,\ell} + v_{1,k,\ell} \mathbf{e}_{1,k,\ell}$ for some $(k,\ell) \in \mathcal{J}$, and $v_{0,k,\ell}^2 + v_{1,k,\ell}^2 = 1$. Let $\mathbf{v} \in \mathcal{V}(A^m)$.
which verifies (M.1'). The fact that only two entries of $\mathbf{v}$ are nonzero and $v_{0,k,\ell}^2 + v_{1,k,\ell}^2 = 1$ implies that
where the last inequality is from the calculation in Equation (ref), and this verifies (M.2') for the third moment. Moreover,
The same logic shows that $\mathbb{E}[\exp(|\mathbf{v}^\top \mathbf{C}_i|/(K\sqrt{n / r_n}))] \leq 2$, where $K$ is an absolute constant. Putting together, we verify conditions (M.2') and (E.1') with $B_n = \sqrt{n / r_n}$. Hence by chernozhukov2017central, there exists mean-zero random vectors $\boldsymbol{D}_i \sim N(\mathbf{0}, \mathbb{E}[\mathbf{C}_i \mathbf{C}_i^\top])$ such that
Observe that for any $k_1, k_2 \in [n], \ell_1, \ell_2 \in [p]$, we have $\operatorname{Cov}[\mathbf{e}_{0,k_1,\ell_1}^\top \mathbf{C}_i, \mathbf{e}_{1, k_2, \ell_2}^\top \mathbf{C}_i] = 0$. The same calculation as Multivariate Case Step 2 for the proof of Theorem (ref) implies we can replace $\boldsymbol{D}_i$ by another mean-zero Gaussian random vector $\mathbf{Z}_i$ such that
We want to show $\frac{1}{\sqrt{n}}\sum_{i = 1}^n \mathbf{Z}_i$ is close to $\frac{1}{\sqrt{n}}\sum_{i = 1}^n \boldsymbol{D}_i$, measured by the probability of taking value in sets from $\mathcal{A}$ defined at Equation (ref). We omit details for simplicity, but illustrate the main skeleton here. As in Step 2, Nazarov inequality implies we only need to work on the $m$-generated convex approximation with $\epsilon$ precision $A^m = A^m(A)$ for $A \in \mathcal{A}$, for a reason given in chernozhukov2017central. Moreover, $\mathbb{P}(\frac{1}{\sqrt{n}}\sum_{i = 1}^n \mathbf{Z}_i \in A^m) = \mathbb{P}((\mathbf{v}^\top (\frac{1}{\sqrt{n}}\sum_{i = 1}^n \mathbf{Z}_i ))_{\mathbf{v} \in \mathcal{V}(A^m)} \leq \mathbf{t})$ for some $\mathbf{t} \in \mathbb{R}^m$. Hence we only need to show
But the definition of $\mathcal{A}$ in Equation (ref) implies for any $A \in \mathcal{A}, \mathbf{v} \in \mathcal{V}(A^m)$, there exists $\mathbf{e}_k, \mathbf{e}_j$ and $v_k^2 + v_j^2 = 1$ such that $\mathbf{v} = v_k \mathbf{e}_k + v_j \mathbf{e}_j$, with
and hence
Together with Equation (ref), we know
The Gaussian-to-Gaussian Comparison result chernozhuokov2022improved them implies
Now we revisit Equation (ref). Consider
with
Equations (ref) and (ref) imply that
The same argument as csorgo1997limit shows that there exists two independent standard Brownian bridges over $[0,1]$, $B_{n,L}$ and $B_{n,R}$, for each $n$, such that
with $\sigma^2 = \mathbb{V}[\varepsilon_i(0)] = \mathbb{V}[\varepsilon_i(1)]$ and $\epsilon_n = o_{\mathbb{P}}((\log \log n)^{-1/2})$. Let $\{U_L(t): t \in \mathbb{R} \}$ and $\{U_R(t): t \in \mathbb{R}\}$ be two independent O-U processes with $\mathbb{E}[U_j(t)] = 0$ and $\mathbb{E}[U_j(s) U_j(t)] = e^{-|s-t|}$, $j = L,R$. Then
Take $N(t) = \lVert (U_L(t), U_R(t)) \rVert_2, t \in \mathbb{R}$. Then a time change and stationarity of O-U process implies
and
An expansion based on horvath1993maximum (Lemma TODO) gives for any $z \in \mathbb{R}$,
Moreover, Gaussian correlation inequality latala2017royen and stationarity of O-U process implies
Putting together and choosing $z^\ast$ that maximizes $z \mapsto \exp(- 2 e^{-z + \log(2 - (b - a))}) - \exp(-2 e^{-z + \log(c)})$, we can get
Symmetry then implies for any $0 < a < b < 1$ and $\ell \in [p]$, we have
Notice that although the splitting criteria is different from the regression tree, once cells are given the estimator given by the fit-based tree is exactly the same as the regression tree (see Section (ref)). Hence result can be proved based on Theorem (ref) and the same logic as Theorem (ref).
Notice that although the splitting criteria is different from the regression tree, once cells are given the estimator given by the fit-based tree is exactly the same as the regression tree (see Section (ref)). Hence result can be proved based on Theorem (ref) and the same logic as Theorem (ref).
Since the tree is constructed by minimizing the objective Equation (ref) iteratively. The empirical risk minimization property Equation (ref) still holds. Hence the result follows from the same argument as the proof of Theorem (ref).
Notice that although the splitting criteria is different from the regression tree, once cells are given the estimator given by the fit-based tree is exactly the same as the regression tree (see Section (ref)). Hence result can be proved based on Theorem (ref) and the same logic as Theorem (ref).
Since the tree is constructed by minimizing the objective Equation (ref) iteratively. The empirical risk minimization property Equation (ref) still holds. Hence the result follows from the same argument as the proof of Theorem (ref).
Notice that although the splitting criteria is different from the regression tree, once cells are given the estimator given by the fit-based tree is exactly the same as the regression tree (see Section (ref)). Hence result can be proved based on Theorem (ref) and the same logic as Theorem (ref).
The result follows from the same argument as Theorem (ref).
First, we consider $\mathtt{X}$ under Assumption (ref). Since $(y_i, d_i)$'s are from dataset $\mathscr{D}_{\tau}$ independent to the dataset $\mathscr{D}_{\mathsf{T}_1}$ to $\mathscr{D}_{\mathsf{T}_K}$ for tree construction, it is easy to check that
Next, we consider $\mathtt{HON}$ under Assumption (ref). Denote by $\mathsf{t}(\mathbf{x})$ the node that contains $\mathbf{x}$, and denote by $n(\mathsf{t})$ the local sample size in $\mathcal{D}_{\tau}$, where $n(\mathsf{t}) = \sum_{i \in \mathcal{D}_{\tau}}\mathds{1}(\mathbf{x}_i \in \mathsf{t})$. Then
where in the third line, we have used the fact that $\varepsilon_i(0)$ and $\varepsilon_i(1)$ in $\mathcal{D}_{\tau}$ are independent to $\mathbf{x}_i$'s in $\mathcal{D}_{\tau}$ and the whole dataset $\mathcal{D}_{\mathsf{T}}$, with $\mathbb{E}[\varepsilon_i(0)] = \mathbb{E}[\varepsilon_i(1)] = 0$. Unconditioning over $\mathcal{D}_{\mathsf{T}}$, then we get
The results for $\mathtt{DIM}$ and $\mathtt{SSE}$ can be obtained by similar arguments.
Finally, we consider $\mathtt{NSS}$ under Assumption (ref) and the additional symmetric error $\varepsilon_i(0)$, and $\varepsilon_i(1)$ assumption. We will use an induction assumption.
Base case: $K = 1$. Due to the assumption that $\mu_0$ and $\mu_1$ are constant, we can rewrite the splitting criteria from Definition 2 in the main paper as
and
and
Denote the vector $\boldsymbol{\varepsilon} = (\varepsilon_1(0), \varepsilon_1(1), \cdots, \varepsilon_n(0), \varepsilon_n(1))$. Notice that for all three criteria, for any $\mathbf{d} = (d_1, \cdots, d_n)$ and $\mathsf{t}_L, \mathsf{t}_R$, $\varepsilon = \mathbf{u}$ and $\varepsilon = - \mathbf{u}$ give the same value. Hence condition on $\mathbf{d}$ and the data-driven split region $\hat{\mathsf{t}}_L$ and $\hat{\mathsf{t}}_R$, $\boldsymbol{\varepsilon}$ is symmetrically distributed around zero. It then follows from the form of the three estimators that all of them are unbiased.
Induction step: $K \geq 2$. Each leaf node $\mathsf{t}$ in layer $K-1$ is further partitioned into $\mathsf{t}_L$ and $\mathsf{t}_R$ such that Equations (ref), (ref) and (ref) are maximized. The induction hypothesis is that condition on all leaf $\mathsf{t}$ in the $K-1$ th layer and $\mathbf{d}$, $\boldsymbol{\varepsilon}$ is symmetrically distributed around zero. Again for all three criteria, given $K-1$th leaf node $\mathsf{t}$, for any $\mathbf{d} = (d_1, \cdots, d_n)$ and $\mathsf{t}_L, \mathsf{t}_R$, $\varepsilon = \mathbf{u}$ and $\varepsilon = - \mathbf{u}$ give the same value. Hence the resulting $K$th level $\hat{\mathsf{t}}_L$ and $\hat{\mathsf{t}}_R$ are such that condition on $\mathbf{d}$ and the data-driven split region $\hat{\mathsf{t}}_L$ and $\hat{\mathsf{t}}_R$, $\boldsymbol{\varepsilon}$ is symmetrically distributed around zero, making the estimators unbiased.