thresholding. Suppose we are partitioning node $A$ into two new leaf nodes $A_1, A_2$. Then the (unsigned) **tree impurity decrease** after this partition is defined as: $$\Delta I_\alpha(T, \mathbb{P}_n) = \mathbb{P}_{n,\alpha}(A) [I_\alpha(A, \mathbb{P}_n) - I_\alpha(A_1,\mathbb{P})\mathbb{P}_{n,\alpha}(A_1|A) -  I_\alpha(A_2,\mathbb{P})\mathbb{P}_{n,\alpha}(A_2|A)].$$ Let $J_0\subset \{1, 2, \ldots d\}$ be the indices of features that have been partitioned in previous tree building steps. Given that we are partitioning on node $A$, let $\Delta I_0$ be the maximal tree impurity decrease over all partitions in feature $X[j], j\in J_0$. Then a partition in a new feature $X[j'], j'\not\in J_0$, with tree impurity decrease $\Delta I_\alpha(T, \mathbb{P}_n)$, is accepted if $$\label{impu decr}
\Delta I_\alpha(T, \mathbb{P}_n) \ge \Delta I_0 + c_0\lambda_n,$$ where $c_0$ is a constant independent of the training data. By equation (\[impu decr\]), a partition on a new feature is accepted if its tree impurity decrease is greater than $\Delta I_0$, the tree impurity decrease over all previously partitioned features, plus a threshold term $c_0\lambda_n$. Theoretical support for this thresholding approach is provided in Section 3.

Computational Complexity
------------------------

Recall the number of training samples is $n$ and the number of features is $d$. Denote the depth of the estimated tree as $h$ and let the maximal 