R(f)$ and $R^* = R(f^*),$ respectively. Without loss of generality, we assume $\mathbb{P}(\mathbb{E}(Y|X)=1/(1+\alpha))=0$. Then the oracle classifier is unique almost surely. We now define the consistency of a sequence of classifiers based on L1 distance from the oracle classifier.

A sequence of classifiers $f_n$ is consistent if $ \lim_{n\to\infty}  \mathbb{E} |f_n - f^*| = 0.$

Denote the tree obtained from Algorithm 1 as $\hat{T}_n$ and the classifier$:\Omega\to\{0,1\}$ associated with $\hat{T}_n$ as $\hat{f}_n$. Theorem \[consistency\] shows $\hat{f}_n$ is consistent under mild conditions.

\[consistency\] Let $\mathbb{P}$ be absolutely continuous with respect to Lebesgue measure on $\mathbb{R}^d$. Assume $\lim_{n\to\infty}\bar{a}_n = \infty,$ $\lim_{n\to\infty}\lambda_n = 0,$ and $\lim_{n\to\infty}\frac{\bar{a}_n d\log n}{n} = 0.$ Let $\alpha$ be a constant no smaller than one. Then the classifier $\hat{f}_n$ obtained from Algorithm 1 is consistent.

Feature Selection Consistency
-----------------------------

Let $X[-j]$ denote the set of all features except $X[j]$. We say $X[j]$ is redundant if conditionally on $X[-j]$, $Y$ is independent of $X[j]$. We denote $X'$ as the collection of all non-redundant features, and $X''$ as the collection of all redundant features. Under two conditions on the distribution of $Y, X'$ and $X''$, we can show if $\lambda_n$ goes to zero slower than $n^{-1/2}$, the probability of $\hat{T}_n$ excluding 