Bound for $L_2$-error of random forest estimate

I am struggling to understand a certain inequality based on the regression $$L_2$$-error of a regression function estimate.

The setting is that of random forests for regression.

• Let $$\Theta = \{ \Theta_{1}, \dots, \Theta_{M} \}$$ be the (iid) random variables that capture the randomness that goes into contructing the individual trees.
• Let $$m(x) = \mathbb{E}\left[ Y ~|~ X=x \right]$$ be the (true, unknown) regression function that we want to estimate with the random forst.
• Assume that trees in the forest are fully grown, i.e. each cell in a tree contains exactly one of the points subsampled/bootstrapped for construction of the tree. Consequently, we can write the regression function estimate of the forest as $$m_{n}(X) = \sum_{i=1}^n W_{ni}(X)Y_{i}$$
• where $$W_{ni}(x) = \mathbb{E}_{\Theta}\left[\mathbb{1}_{x_{i}\in A_{n}(x, \Theta_{j})}\right]$$

• and $$A_n(x, \Theta)$$ is the cell of $$x$$ in a tree generated via $$\Theta$$.

Now, the inequality in question is the following. It's from the proof of Theorem 2 in Scornet2015.

$$\mathbb{E}\left[m_{n}(X) - m(X) \right]^2 \leq 2 \mathbb{E}\left[ \sum_{i=1}^n W_{ni}(X)(Y_{i}-m(X_{i})) \right]^2 + 2 \mathbb{E}\left[ \sum_{i=1}^n W_{ni}(X)(m(X_{i})-m(X)) \right]^2$$

My first question is: Why is that? I have tried applying the basic textbook error decompositions but am not getting anywhere.

My second question is: In the publication, the authors refer to the first term as the "estimation error" and the second as the "approximation error". This does not quite fit with my current understanding of these terms:

• Estimation error: Error of selected function as compared to best possible choice from hypothesis class
• Approximation error: Error of best possible from hypothesis class as compared to true regression function

Getting an intuition on the second question is probably more important to me.

For your first question, the trick is to write $$m(X) =\sum_{i=1}^n W_{ni}(X)m(X)$$, which then gives :

\begin{align*} \mathbb{E}\left[m_{n}(X) - m(X) \right]^2 &= \mathbb{E}\left[\sum_{i=1}^n W_{ni}(X)(Y_{i} - m(X)) \right]^2\\ &= \mathbb{E}\left[\sum_{i=1}^n W_{ni}(X)(Y_{i} - m(X_i) + m(X_i) - m(X)) \right]^2\\ \end{align*}

Now we write $$a_i := W_{ni}(X)(Y_i - m(X_i))$$, $$b_i:=W_{ni}(X)(m(X_i) - m(X))$$, and using the inequality $$\left(\sum_{1\le i\le n} a_i + b_i\right)^2 \le 2\left(\sum_{1\le i\le n} a_i\right)^2 + 2\left(\sum_{1\le i\le n} b_i\right)^2$$ (which can be proven by recurrence, starting from the well known $$(a+b)^2 \le 2a^2 + 2b^2$$), we immediately get \begin{align*} \mathbb{E}\left[m_{n}(X) - m(X) \right]^2 &=\mathbb{E}\left[\sum_{i=1}^n a_i + b_i \right]^2 \\ &\le 2\mathbb{E}\left[\sum_{i=1}^n a_i \right]^2 + 2\mathbb{E}\left[\sum_{i=1}^n b_i\right]^2 \end{align*}

As desired.

For your second question, I agree with your definitions of "estimation error" and "approximation error". I am not very familiar with regression trees and the notations used in the paper, but let me nonetheless try to explain why they named these two terms as they did :

• The term $$I_n := \mathbb{E}\left[\sum_{i=1}^n a_i \right]^2$$ represents the $$L^2$$ error between the estimator $$m_n := \sum_{i=1}^n W_{ni}(X) Y_i$$ and the "best possible tree" $$m_{best} := \sum_{i=1}^n W_{ni}(X) m(X_i)$$ (I admit that I'm not 100% sure that $$m_{best}$$ is indeed the best tree, I strongly suspect it to be true though). That indeed corresponds to the definition of the estimation error between our estimator and the best possible estimator in the given hypothesis class.

• The term $$J_n := \mathbb{E}\left[\sum_{i=1}^n b_i \right]^2$$ corresponds to the $$L^2$$ error between the estimator $$m_{best}$$ as defined above and the actual regression function $$m:= \mathbb E[Y\mid X=\cdot]$$. Again, admitting that $$m_{best}$$ is the best estimator in our hypothesis class, this corresponds exactly to the definition of approximation error you gave.

• Thank you very much for this well-written answer, that's everything I could have hoped for. Ah well, the very first step is what eluded me, for whatever reason. Apr 7, 2023 at 20:52