Asymptotic Normality and Inference for Forests

Summary

Wager & Athey (2018) prove that predictions of a subsampled, honest, regular, random-split forest are asymptotically Gaussian and centered at the truth: $({\hat{\mu }}_n(x)-\mu (x))/{\sigma }_n(x)\Rightarrow \mathcal{N}(0,1)$ provided the subsample size scales as $s_n\asymp n^{\beta }$ with ${\beta }_{\min }<\beta <1$ (Theorem 1), and the same holds for causal-forest estimates $\hat{\tau }(x)$ under unconfoundedness and overlap (Theorem 11). The proof has two halves: honesty + Lipschitz continuity bound the bias by a power of $s$ (leaf diameters shrink), and subsampling makes the forest a U-statistic close to its Hájek projection, a sum of independent terms. The variance is consistently estimated by the infinitesimal jackknife ${\hat{V}}_{IJ}$. Athey, Tibshirani & Wager (2019) extend the result to any GRF estimate $\hat{\theta }(x)$ by coupling it to an infeasible pseudo-forest of influence functions, with variance ${\sigma }_n^2(x)=\mathrm{polylog}(n/s{)}^{-1}s/n$ estimated by the bootstrap of little bags.

Overview

A pointwise confidence interval $\hat{\tau }(x)\pm 1.96{\hat{\sigma }}_n(x)$ is valid only if (i) $\hat{\tau }(x)$ is asymptotically normal, (ii) its bias is negligible relative to its standard deviation, and (iii) ${\hat{\sigma }}_n$ is consistent. For adaptive ML estimators (ii) is the hard part; classical nonparametrics handles it by undersmoothing. For forests the tuning knob is the subsample size $s$: a larger $s$ gives deeper trees, smaller leaves and less bias but more correlated trees and higher variance (${\sigma }_n^2\approx s/n$ up to logs). The theorems identify the window of $\beta =\log s/\log n$ in which bias${}^2\ll$ variance.

Main Content

Random forest as a U-statistic (Definition 1) ^def-rf-ustat

With base learner $T$, auxiliary randomness $\xi \sim \Xi$ and subsample size $s$,

$$\mathrm{RF}(x;Z_1,\dots ,Z_n)={\left(\genfrac{}{}{0ex}{}{n}{s}\right)}^{-1}\sum _{1\le i_1<\cdots <i_s\le n}{\mathbb{E}}_{\xi \sim \Xi }[T(x;\xi ,Z_{i_1},\dots ,Z_{i_s})],$$

approximated in practice by Monte Carlo over $B$ subsamples drawn without replacement. The theory assumes $B$ large enough that Monte Carlo error is negligible (Wager et al. recommend $B$ of order $n$).

Theorem 1 (regression forests) and Theorem 11 (causal forests) ^thm-forest-clt

Let $Z_i=(X_i,Y_i)$ be i.i.d. with $X_i\sim U([0,1{]}^d)$ (or a density bounded away from 0 and $\infty$); $\mu (x)=\mathbb{E}[Y\mid X=x]$ and ${\mu }_2(x)=\mathbb{E}[Y^2\mid X=x]$ Lipschitz; $\mathrm{Var}[Y\mid X=x]>0$; $\mathbb{E}[|Y-\mathbb{E}[Y\mid X=x]{|}^{2+\delta }\mid X=x]\le M$. Let $T$ be honest, $\alpha$-regular with $\alpha \le 0.2$, symmetric and random-split (each feature chosen with probability $\ge \pi /d$). If

$$s_n\asymp n^{\beta }\text{for some}{\beta }_{\min }:=1-(1+\frac{d}{\pi }\frac{\log ({\alpha }^{-1})}{\log ((1-\alpha {)}^{-1})}{)}^{-1}<\beta <1,$$

then there is a sequence ${\sigma }_n(x)\to 0$ with

$$\frac{{\hat{\mu }}_n(x)-\mu (x)}{{\sigma }_n(x)}\Rightarrow \mathcal{N}(0,1)\text{and}{\hat{V}}_{IJ}(x)/{\sigma }_n^2(x){\to }_{p}1.$$

Theorem 11: if additionally treatment is unconfounded, overlap holds, and both $(X_i,Y_i^{(0)})$ and $(X_i,Y_i^{(1)})$ satisfy the regularity conditions above, the same conclusions hold for $\hat{\tau }(x)$ from a causal forest built from honest, $\alpha$-regular (Definition 4b) causal trees. If $s$ grows more slowly than the bound, the forest is still asymptotically normal but may be asymptotically biased.

Note how ${\beta }_{\min }\to 1$ as $d\to \infty$: in high dimension the admissible window closes and the rate ${\sigma }_n^2\approx n^{\beta -1}$ becomes very slow — the curse of dimensionality shows up as a constraint on honest inference, consistent with coverage deteriorating beyond $d\approx 10$ in the simulations of Honest Trees and Causal Forests.

Half 1 — bias (§3.2)

Lemma 2 and Theorem 3 — leaf diameter and bias ^thm-forest-bias

For a regular, random-split tree on $X_i\sim U([0,1{]}^d)$, the leaf diameter along each coordinate $j$ satisfies, for large $s$ and any $0<\eta <1$, ${\mathrm{diam}}_j(L(x))\lesssim (s/(2k-1){)}^{-0.99(1-\eta )\frac{\log ((1-\alpha {)}^{-1})}{\log ({\alpha }^{-1})}\frac{\pi }{d}}$ with high probability. If moreover $\mu$ is Lipschitz and the trees are honest, then for $\alpha \le 0.2$

$$|\mathbb{E}[\hat{\mu }(x)]-\mu (x)|=O\left(s^{-\frac{1}{2}\frac{\log ((1-\alpha {)}^{-1})}{\log ({\alpha }^{-1})}\frac{\pi }{d}}\right).$$

Honesty is what converts “small leaf” into “small bias”: conditional on the partition, held-out leaf means are unbiased for the leaf’s average of $\mu$, so the only bias is $\mu$‘s variation within the leaf. Because a forest is an average of identically distributed trees, the forest’s bias equals a single tree’s bias — averaging reduces variance, never bias — which is why bias must be controlled at tree level.

Half 2 — Gaussianity via Hájek projections (§3.3)

The Hájek projection $\mathring{T}=\mathbb{E}[T]+{\sum }_{i=1}^n(\mathbb{E}[T\mid Z_i]-\mathbb{E}[T])$ captures the first-order (additive) part of $T$; it is a sum of independent variables and hence asymptotically normal. If $\mathrm{Var}[\mathring{T}]/\mathrm{Var}[T]\to 1$, $T$ inherits normality. Individual trees do not satisfy this, so Wager & Athey introduce a weaker notion.

$\nu$-incrementality (Definition 6)

$T$ is $\nu (s)$-incremental at $x$ if $\mathrm{Var}[\mathring{T}(x;Z_1,\dots ,Z_s)]/\mathrm{Var}[T(x;Z_1,\dots ,Z_s)]\gtrsim \nu (s)$.

Viewing trees as $k$-potential-nearest-neighbor predictors (Lin & Jeon 2006) — $T(x)={\sum }_i{S}_i{Y}_i$ with selection weights $S_i$ that, under honesty, are independent of $Y_i$ given $X_i$ — Lemma 4 shows $s\mathrm{Var}[\mathbb{E}[S_1\mid Z_1]]\gtrsim \frac{1}{k}{C}_{f,d}/\log (s{)}^d$, and Theorem 5 concludes that honest $k$-regular symmetric trees are $\nu (s)$-incremental with $\nu (s)=C_{f,d}/\log (s{)}^d$ ($C_{f,d}=2^{-(d+1)}(d-1)!$ for uniform $f$; Corollary 6 gives $C_{f,d}/(4\log (s{)}^d)$ for double-sample trees). Then subsampling amplifies weak incrementality to full incrementality:

Lemma 7, Theorems 8–9 ^thm-subsampling

For the forest $\hat{\mu }$ with Hájek projection $\mathring{\hat{\mu }}$ (Efron–Stein ANOVA decomposition),

$$\mathbb{E}[(\hat{\mu }(x)-\mathring{\hat{\mu }}(x){)}^2]\le (\frac{s}{n}{)}^2\mathrm{Var}[T(x;\xi ,Z_1,\dots ,Z_s)].$$

Hence if $s_n\to \infty$ and $s_n\log (n{)}^d/n\to 0$, then $({\hat{\mu }}_n(x)-\mathbb{E}[{\hat{\mu }}_n(x)])/{\sigma }_n(x)\Rightarrow \mathcal{N}(0,1)$ (Thm 8), and the infinitesimal jackknife is consistent, ${\hat{V}}_{IJ}/{\sigma }_n^2{\to }_{p}1$ (Thm 9).

Combining: variance $\approx s/n$ (up to logs), squared bias $\approx s^{-\frac{\log ((1-\alpha {)}^{-1})}{\log ({\alpha }^{-1})}\frac{\pi }{d}}$; requiring bias${}^2/$variance $\to 0$ yields exactly the lower bound ${\beta }_{\min }$.

Infinitesimal jackknife variance estimator (eq. 8) ^def-ij

$${\hat{V}}_{IJ}(x)=\frac{n-1}{n}\left(\frac{n}{n-s}{)}^2\sum _{i=1}^n{\mathrm{Cov}}_{\ast }\right[{\hat{\tau }}_b^{\ast }(x),N_{ib}^{\ast }{]}^2,$$

where ${\hat{\tau }}_b^{\ast }(x)$ is tree $b$‘s estimate, $N_{ib}^{\ast }\in \{0,1\}$ indicates whether example $i$ was in tree $b$‘s subsample (either half, for double-sample trees), and the covariance is over trees. The factor $n(n-1)/(n-s{)}^2$ is a finite-sample correction for subsampling without replacement: for trivial no-split trees it makes ${\hat{V}}_{IJ}$ equal to the usual unbiased variance of a sample mean (Proposition 10).

Extension to generalized random forests (ATW 2019, §3–4)

$\hat{\theta }(x)$ solves a weighted moment equation and is not an average of trees, so the U-statistic argument does not apply directly. Under Assumptions 1–6 (Lipschitz $x$-signal $M_{\theta ,\nu }(x)=\mathbb{E}[{\psi }_{\theta ,\nu }(O)\mid X=x]$; smooth identification with invertible $V(x)={\partial }_{(\theta ,\nu )}M$; Lipschitz variogram; regularity of $\psi$; existence of approximate solutions; convexity) and Specification 1:

ATW Theorem 3, Lemma 4, Theorem 5 ^thm-grf-clt

(i) $(\hat{\theta }(x),\hat{\nu }(x)){\to }_p(\theta (x),\nu (x))$. (ii) Define influence functions ${\rho }_i^{\ast }(x)=-{\xi }^{\top }V(x{)}^{-1}{\psi }_{\theta (x),\nu (x)}(O_i)$ and the infeasible pseudo-forest ${\tilde{\theta }}^{\ast }(x)=\theta (x)+{\sum }_i{\alpha }_i(x){\rho }_i^{\ast }(x)$ — formally a regression forest with outcomes $\theta (x)+{\rho }_i^{\ast }(x)$, hence a U-statistic. With $s=n^{\beta }$ and ${\beta }_{\min }:=1-(1+{\pi }^{-1}\log ({\omega }^{-1})/\log ((1-\omega {)}^{-1}){)}^{-1}<\beta <1$,

$$\sqrt{n/s}\Vert {\tilde{\theta }}^{\ast }(x)-\hat{\theta }(x){\Vert }_2=O_P\left(\max \right\{s^{-\frac{\pi }{2}\frac{\log ((1-\omega {)}^{-1})}{\log ({\omega }^{-1})}},(s/n{)}^{1/6}\}).$$

(iii) If $\mathrm{Var}[{\rho }_i^{\ast }(x)\mid X_i=x]>0$, then $({\hat{\theta }}_n(x)-\theta (x))/{\sigma }_n(x)\Rightarrow \mathcal{N}(0,1)$ with ${\sigma }_n^2(x)=\mathrm{polylog}(n/s{)}^{-1}s/n$.

Variance by the delta method. $\mathrm{Var}[{\tilde{\theta }}^{\ast }(x)]={\xi }^{\top }V(x{)}^{-1}{H}_n(x)(V(x{)}^{-1}{)}^{\top }\xi$ with $H_n(x)=\mathrm{Var}[{\sum }_i{\alpha }_i(x){\psi }_{\theta (x),\nu (x)}(O_i)]$; estimate ${\hat{\sigma }}_n^2={\xi }^{\top }{\hat{V}}_n^{-1}{\hat{H}}_n({\hat{V}}_n^{-1}{)}^{\top }\xi$. $V(x)$ is a problem-specific curvature ($f_x(\theta (x))$ for quantiles; the $2\times 2$ matrix of conditional moments for IV), estimated by auxiliary honest regression forests.

Bootstrap of little bags for $H_n$ (§4.1, Theorem 6)

The ideal estimator is half-sampling: recompute the forest score $\Psi$ on all half-samples $\mathcal{H}$, ${\hat{H}}_n^{HS}={\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)}^{-1}{\sum }_{\mathcal{H}}({\Psi }_{\mathcal{H}}-\Psi {)}^2$ — infeasible. Instead (Sexton & Laake 2009):

1. Draw $g=1,\dots ,B/\ell$ random half-samples ${\mathcal{H}}_g$; grow trees in little bags of $\ell \ge 2$, all trees in bag $g$ subsampling from ${\mathcal{H}}_g$.
2. Use the ANOVA identity ${\mathbb{E}}_{ss}[(\frac{1}{\ell }{\sum }_{b=1}^{\ell }{\Psi }_b-\Psi {)}^2]={\hat{H}}_n^{HS}+\frac{1}{\ell -1}{\mathbb{E}}_{ss}[\frac{1}{\ell }{\sum }_{b=1}^{\ell }({\Psi }_b-\frac{1}{\ell }{\sum }_{b^{\prime }}{\Psi }_{b^{\prime }}{)}^2]$: between-bag variance minus the within-bag Monte Carlo term estimates ${\hat{H}}_n^{HS}$ at almost no extra cost.

Theorem 6: ${\hat{H}}_n^{HS}$ is consistent and the resulting Gaussian intervals have asymptotically nominal coverage. For small $B$ the moment estimate can be negative; grf uses a Bayesian ANOVA with an improper uniform prior on $[0,\infty )$.

Scope and caveats. (1) The guarantees are pointwise in $x$, not uniform bands, and Remark 4 (W&A) notes regularity cannot hold at all $x$ simultaneously; scanning for the subgroup with the largest $\hat{\tau }(x)$ reintroduces a multiple-comparisons problem (Multiple Testing Corrections). (2) Covariates are fixed-dimensional; “asymptotic normality of random forests in high dimensions” is left to future work. (3) The nuisance estimates $\hat{\nu }(x)$ are also asymptotically normal, but “tree splits are not necessarily targeted to expressing heterogeneity in $\nu (x)$,” so they may be inaccurate. (4) In practice coverage fails through bias, not variance (sharp peaks, boundaries, large $d$).

Examples

Reading ${\beta }_{\min }$. With balanced-ish splits $\alpha =0.2$: $\log ({\alpha }^{-1})/\log ((1-\alpha {)}^{-1})=1.609/0.223\approx 7.2$. For $d=2$ and fully random feature choice ($\pi =1$): ${\beta }_{\min }=1-(1+14.4{)}^{-1}\approx 0.935$. For $d=10$: ${\beta }_{\min }\approx 0.986$. So theory asks for subsamples nearly as large as $n$ (deep trees) — e.g. the paper’s Simulation 2 uses $n=5000$, $s=2500$ — and the resulting rate $n^{-(1-\beta )/2}$ is slow. These are worst-case sufficient conditions under mere Lipschitz smoothness; they do not exploit the forest’s adaptivity to sparse signals.

Empirical check of Gaussianity (W&A Fig. 1). In the confounded design with $n$ growing, the sampling variance ${\sigma }_n^2(x)$ falls with $n$, the relative RMSE of ${\hat{V}}_{IJ}$ decays, and standardized $\hat{\tau }(x)$ values across 1,000 test points track the Gaussian QQ line.

Minimal IJ computation.

# tau_b: (B,) per-tree estimates at x;  N: (B, n) 0/1 inclusion matrix; s = subsample size
cov = ((N - N.mean(0)) * (tau_b - tau_b.mean())[:, None]).mean(0)   # Cov_* over trees, per i
V_IJ = (n - 1) / n * (n / (n - s)) ** 2 * np.sum(cov ** 2)
ci = tau_b.mean() + np.array([-1.96, 1.96]) * np.sqrt(V_IJ)

Connections

• Honest Trees and Causal Forests — supplies the honest, regular trees these theorems require.
• Generalized Random Forests - Local Moment Equations — the estimator to which the pseudo-forest coupling applies; the pseudo-outcomes ${\rho }_i$ used for splitting are the feasible analogues of the ${\rho }_i^{\ast }$ used for theory.
• Cross-Fitting and Sample Splitting — DML obtains $\sqrt{N}$-normality for a scalar by splitting across folds; forests obtain $\sqrt{n/s}$-normality for a function value by splitting within trees.
• Neyman Orthogonality — influence functions play the linearizing role in both theories (DML’s $\bar{\psi }$; GRF’s ${\rho }_i^{\ast }$).
• T-Learner and Minimax Rate, X-Learner — rate results for metalearners concern MSE, not distributional limits; this note is the vault’s source for pointwise CIs on CATEs.
• Nonparametric Causal Inference — BART’s posterior credible intervals are the Bayesian alternative; their frequentist coverage is not guaranteed by these theorems.

See Also

• Simultaneous Inference via Multiplier Bootstrap — uniform (simultaneous) bands in a different setting; forests currently offer only pointwise intervals.
• Permutation Tests and Exact Inference — resampling for exact tests vs. half-sampling for variance estimation.
• Power Analysis and Sample Size — with ${\sigma }_n^2\approx s/n$, detecting heterogeneity requires far larger samples than detecting an average effect.
• Source for the GRF results: Athey Tibshirani Wager 2019 - Generalized Random Forests.